ساعت‌کاری سنگین


  • محدودیت زمان:‌ ۱ ثانیه
  • محدودیت حافظه: ۱۰۲۴ مگابایت

صورت سوال و ورودی‌ها در این سوال دقیقاً با ساعت‌کاری سبک برابر است. تنها تفاوت این دو سوال، خروجی‌ای‌ست که شما بایستی چاپ کنید.

در شرکت کوئرا nn نفر مشغول به کارند که جز باقر (رئیس شرکت) هر نفر بالادستی‌ای دارد. به مجموعه‌ی هر فرد و زیردستانش و زیردستانِ زیردستانش و... تیم او می‌گوییم. مثلاً تیم باقر برابر کل اعضای شرکت است. در واقع ساختار شرکت شبیه یک جنگل (گراف جهت‌دار بدون دور) است.

این روزها کوئرا با mm پروژه‌ی سخت و نفس‌گیر دست و پنجه نرم می‌کند. اعضای کوئرا شدیدن مشغولند و وقت سر خاراندن‌شان نیست. هر پروژه تعدادی زیرپروژه دارد. به مجموعه‌ی هر پروژه و زیرپروژه‌هایش و زیرپروژه‌های زیرپروژه‌هایش و... پراجکت‌باکس آن پروژه می‌گوییم. در واقع ساختار پروژه‌ها شبیه یک جنگل (گراف جهت‌دار بدون دور) است.

سِپَسَک، سامانه‌ی پردازش ساعت‌های کاری، ایده‌ای بدیع از استاد باقر است که قرار است اثر چشم‌گیری در رشد و پیش‌رفت شرکت مذکور داشته باشد. داستان از این‌جا شروع می‌شود که شما باید این سیستم را بنویسید.

پس از گذشت چند سال از شروع به کار کوئرا هم اکنون اعضای خوش‌تلاش کوئرا همه‌ی پروژه‌ها را تحویل داده اند. باقر ساعت‌های کاری شرکت از بدو شروع به کار کوئرا را در ورودی به شما تحویل می‌دهد. شما باید در راستای تکمیل سپسک تحلیل‌هایی بر روی ساعت‌های کاری اعضای کوئرا انجام دهید.

ورودی🔗

در خط اول ورودی دو عدد nn و mm و kk آمده است که تعداد اعضای شرکت و تعداد پروژه‌ها و تعداد رکوردها را نشان می‌دهد.

در خط بعد n1n-1 عدد آمده‌ست که iiامین آن‌ها شماره‌ی بالادستی نفر i+1i+1ام را نشان می‌دهد. دقت کنید شماره‌ی باقر ۱ می‌باشد و بالادستی ندارد.

در خط بعد mm عدد آمده‌ست که iiامین آن‌ها شماره‌ی پروژه‌ای که شامل پروژه‌ی iiام می‌شود را نشان می‌دهد. اگر پروژه‌ی دیگری شامل این پروژه نشود این عدد برابر صفر خواهد بود.

در خط بعد mm عدد آمده‌ست که iiامین آن‌ها سود پروژه‌ی iiام را نشان می‌دهد. دقت کنید سود هر پروژه مستقل از زیرپروژه‌های آن است.

در ادامه kk خط می‌آید که هر کدام یک رکورد ساعت‌کاری‌ست. هر رکورد به فرمت YY/MM/DD hh:mm:ss Person Project Type است که Person برابر شماره‌ی فرد است، Project شماره‌ی پروژه‌ست و Type برابر Start یا End است که نشان‌دهنده‌ی این است که این رکورد شروع یا پایان یک ساعت کاری را نشان می‌دهد.

1n,m,k300 0001 \le n, m, k \le 300\ 000

شماره‌ی بالادستی هر نفر از خودش کوچک‌تر است.

شماره‌ی پروژه‌ی شامل‌شونده‌ی پروژه‌ی دیگر (در صورت وجود) از آن کوچک‌تر است.

کوئرا در سال ۹۴ تاسیس شد و تاریخ پیش از آن به شما داده نخواهد شد. همچنین تاریخی پس از سال ۹۸ نیز به شما داده نخواهد شد.

هر بازه‌ای از ساعت کاری که شروع شده است لزوماً تمام هم شده است و kk زوج است.

سود هیچ پروژه‌ای از ۱ میلیارد بیشتر نیست.

ممکن نیست یک نفر هم‌زمان در حال انجام چند کار باشد.

خروجی🔗

در خط اول nn عدد چاپ کنید که iiامین آنها میزان کار انجام شده توسط تیم نفر ii است. این زمان‌ها را با فرمت h:mm:ss چاپ کنید (تعداد ارقام بخش ساعت اهمیتی ندارد، ولی اگر صفر باشد باید صفر را چاپ کنید، مثلاً اگر کسی ۱۳ دقیقه و ۱۷ ثانیه کار کرده باشد باید 0:13:17 چاپ کنید).

در خط بعد mm عدد چاپ کنید که iiامین آنها میزان کار انجام شده بر روی پراجکت‌باکس ii است. این زمان‌ها را با فرمت h:mm:ss چاپ کنید.

در خط بعد بیشترین کار انجام شده توسط کل اعضای شرکت در بازه‌ای به طول ۲۴ ساعت را چاپ کنید.

در خط بعد سودی که هر شخص شرکت عاید شرکت کرده‌ست را به تومان چاپ کنید. سودی که یک نفر عاید شرکت کرده‌ست برابر جمع سود پروژه‌هایی‌ست که او انجام داده است. همچنین اگر شخصی بخشی از یک پروژه را انجام داده باشد به همان کسری از پروژه که انجام داده است به شرکت سود رسانده است. در واقع اگر این شخص مجموعاً AA ثانیه روی این پروژه کار کرده باشد و کل پروژه TT ثانیه وقت برده باشد و سود آن SS باشد این شخص AT×S\frac{A}{T} \times S سود عاید شرکت کرده است. برای مثال اگر فرد ۱۳۱ ثانیه روی پروژه‌ای که مجموعاً ۳۱۳ ثانیه وقت برده است و ۱۳ تومان سود برای کوئرا داشته است کار کرده باشد (و روی پروژه‌ی دیگری کار نکرده باشد) شما باید 5.440894 را چاپ کنید. اختلاف مطلق و نسبی شما با جواب درست نباید بیش از 10410^{-4} باشد. در واقع اگر جواب شما pp و جواب درست jj باشد، در صورتی جواب شما درست در نظر گرفته می‌شود که pjmax(j,1)104\frac{|p - j|}{max(j, 1)} \le 10^{-4}.

زیرمسئله‌ها🔗

زیرمسئله نمره محدودیت
۱ ۱۵ تنها باید خط اول از خروجی شما صحیح باشد
۲ ۱۵ تنها باید خط دوم از خروجی شما صحیح باشد
۳ ۳۰ تنها باید خط سوم از خروجی شما صحیح باشد
۴ ۴۰ تنها باید خط چهارم از خروجی شما صحیح باشد

دقت کنید شما باید دقیقاً ۴ خط چاپ کنید. به ازای درست بودن هر کدوم از این خطوط نمره‌ی مشخص شده را دریافت خواهید کرد. تست‌های ۱ و ۲ و ۳ و ۴ همان ورودی نمونه هستند و در هر کدام درست بودن همان خط بررسی می‌شود. تست‌های ۵ و ۶ و ۷ و ۸ نیز به ترتیب مربوط به خطوط ۱ و ۲ و ۳ و ۴ هستند. مثلاً اگر شما خط سوم خروجی‌تان درست باشد باید تست‌های ۳ و ۷ را درست جواب بدهید.

مثال🔗

ورودی نمونه🔗

3 3 10
1 2
0 1 0
56 62 56
97/06/03 20:09:33 1 3 Start
97/06/03 20:19:57 3 2 Start
97/06/04 23:13:14 3 2 End
97/06/04 23:15:54 1 3 End
97/07/02 10:09:33 2 1 Start
97/07/02 10:15:54 2 1 End
97/07/03 23:09:33 1 2 Start
97/07/03 23:19:57 3 2 Start
97/07/04 01:13:14 3 2 End
97/07/04 01:15:54 1 2 End
Plain text

خروجی نمونه🔗

58:05:37 28:52:55 28:46:34 
30:59:16 30:52:55 27:06:21 
48:00:00
60.227767 56.000000 57.772233 
Plain text
ارسال پاسخ برای این سؤال
در حال حاضر شما دسترسی ندارید.