المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره‌ی انتخاب تیم:دوره‌ی ۲۴:سوال ۹

Animals

آلودگی محیط زیست و تخریب گسترده‌ی جنگل‌ها، باعث شده که حیوانات با یکدیگر متحد شده و به شهرها حمله کنند. آن‌ها هر روز در یکی از شهرها هستند و آن را تخریب می‌کنند و سپس به شهری دیگر می‌روند. جاده‌های بین شهرها یک‌طرفه هستند و عجیب این که حیوان‌ها هیچ‌گاه از یک جاده در جهت مخالف استفاده نمی‌کنند. دقت کنید که حیوان‌ها بی‌حرکت نمی‌مانند و در انتهای هر روز، از یکی از جاده‌های خروجی شهر حرکت کرده و رورز بعد به شهری که در طرف دیگر جاده قرار دارد، می‌رسند. ممکن است یک شهر به خودش جاده داشته باشد و ممکن است حیوان‌ها از چنین جاده‌هایی نیز عبور کنند. هم‌چنین می‌دانیم که هر شهر حداقل یک جاده‌ی خروجی دارد.

ستاد بحران تشکیل شدهو این ستاد نیاز دارد تخمینی برای میزان خطری که شهرها را تهدید می‌کند، داشته باشد. ضریب خطر شهر $x$ را برابر با حد عبارت $\frac{|S_x(k)}{k}$ زمانی که $k$ به سمت بی‌نهایت می‌رود. تعریف می‌کنیم به طوری که $S_x(k)$ مجموعه‌ی تمام اعداد طبیعی مانند $i$ است که در هر دو شرط زیر صدق می‌کنند:

  • $1\leq I \leq k$
  • حداقل یک حالت وجود دارد که حیوانات با شروع از شهر $x$ و بعد از طی کردن دقیقا $i$ جاده به شهر $x$ بازگردند.

در راستای کمک به ستاد بحران، برنامه‌ای بنویسید که ضریب خطر تمامی شهرها را محاسبه کند.

ورودی

در سطر اول ورودی دو عدد طبیعی $n$، تعداد شهرها و $e$، تعداد جاده‌های یک طرفه، آمده است.($1\leq n,e \leq 5\times 10^5$)

در هر یک از $e$ سطر بعدی به ترتیب دو عدد طبیعی $u$ و $v$ آمده است که نشان‌دهنده‌ی یک جاده‌ی یک‌طرفه از $u$ به $v$ است. ممکن است یک شهر به خودش جاده داشته باشد و هم‌چنین امکان این که بین دو شهر در یک جهت بیش از یک جاده وجود داشته باشد، هست. هم‌چنین تضمین می‌شود که هر شهر حداقل یک جاده‌‌ی خروجی دارد.($1\leq u,v \leq n$)

خروجی

تنها سطر خروجی شامل $n$ کسر ساده‌نشدنی است به طوری که کسر $i$- ام میزان ضریب خطر شهر $i$ است. در صورتی که ضریب خطر شهری ۰ باشد، از نمایش ۰/۱ استفاده کنید.

محدودیت‌ها

  • محدودیت زمان: ۲ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت

ورودی و خروجی نمونه

ورودی نمونه خروجی نمونه
3 3
1 2
2 3
3 1
1/3 1/3 1/3
3 3
1 2
2 3
3 2
0/1 1/2 1/2
7 8
1 2
2 3
3 1
1 4
4 5
5 6
6 1
7 7
1/1 1/1 1/1 1/1 1/1 1/1 1/1

شرح ورودی و خروجی نمونه

در ورودی نمونه‌ی اول، $S_1(k)=\{3\times i |3 \times i \leq k, i \in N\}$ است.

در ورودی نمونه‌ی سوم $S_1(4)=\{3,4\}،S_1(3)=\{3\}،S_1(1)= \emptyset$ و $S_1(7)=\{3,4,6,7\}$ است.


ابزار صفحه