المپدیا

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

ابزار کاربر

ابزار سایت


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

Shora

شورای «کماک» $n$ عضو دارد که با اعداد $0$ تا $n - 1$ شماره‌گذاری شده‌اند. اعضای شورا برای برقراری ارتباط با یکدیگر از اینترنت استفاده می‌کنند. بین برخی از اعضا مسیر ارتباطی وجود دارد که هر کدام از آن‌ها با کلمه‌ی عبوری متفاوت از سایر مسیرها، محافظت می‌شود. توجه کنید که ممکن است بیش از یک مسیر ارتباطی بین دو عضو از شورا برقرار باشد. کلمه‌ی عبور مربوط به هر مسیر ارتباطی در خطی جداگانه از فایل «معما» در سرور کماک ذخیره شده‌اند.

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

رضا از شما خواسته است تا برنامه‌ای بنویسید که مشخص کند چند بازه‌ی کافی در معما وجود دارد.

پیاده‌سازی

در این سوال شما باید توابع زیر را پیاده‌سازی کنید.

  • long long countIntervals(int n, int m, int u[], int v[])

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

  • $n$:تعداد اعضای کماک
  • $m$:تعداد مسیرهای ارتباطی
  • $u, v$:دو آرایه به طول $m$. به ازای هر $i$ $ (0 \le i \le m - 1)$ یک مسیر ارتباطی بین $u_i$ و $v_i$ وجود دارد که کلمه‌ی عبور مربوط به این مسیر ارتباطی در خط $i$ ام فایل معما آمده است.

ارزیاب نمونه

ارزیاب نمونه ورودی را به صورت زیر می‌خواند: در خط اول دو عدد $n$ و $m$ آمده است. سپس $m$ خط آمده است که در خط $i + 1$ ام $u_i$ و $v_i$ آمده‌اند.

زیرمسئله‌ها

  • زیرمسئله‌ی اول (۳۶ نمره): ‎$n = 4$‎.
  • زیرمسئله‌ی دوم (۶۴ نمره): بدون محدودیت اضافی .

محدودیت‌ها

  • محدودیت زمان: ۲ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت
  • $1 \le n \le 10^5$
  • $1 \le m \le 10^5$
  • $0 \le u_i, v_i \le n - 1$
  • $u_i \ne v_i$

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

ورودی نمونه خروجی نمونه
3 5
0 1
1 2
2 1
0 1
0 2
9

ابزار صفحه