المپدیا

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

ابزار کاربر

ابزار سایت


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

Galaxy

دانشمندان نجوم و اخترفیزیک به روابط عجیبی بین کهکشان‌ها پی برده‌اند. آن‌ها $n$ کهکشان پیدا کرده‌اند که هر کدام متشکل از $2^m$ ستاره با شماره‌های 0 تا $2^m-1$ هستند. طبق مشاهده‌ی دانشمندان هرازگاهی بین دو کهکشان پدیده‌ی «پیوندسازی شیری» با یک سه‌تایی $(x,y,p)$ قابل نمایش است. یک پیوندسازی شیری با مشخصه‌ی $(x,y,p)$ به این معنا است که بین کهکشان‌های $x$ و $y$ و به ازای هر $i$ و $j$ که $i\oplus j$ برابر $p$ است ($\oplus$ نماد عملگر $xor$ است) یک راه شیری بین ستاره‌ی شماره‌ی $i$ از کهکشان $x$ و ستاره ی شماره‌ی $j$ از کهکشان $y$ ایجاد می‌شود. پیوندسازی هم تنها بین کهکشان‌های مختلف روی می‌دهد و یک کهکشان مختلف روی می‌دهد و یک کهکشان نمی‌تواند با خودش پیوندسازی شیری انجام دهد. دقت کنید که راه شیری کهکشان نیست بلکه یک «مسیر بین کهکشانی» است.

اگر هر یک از ستارگان را یک راس و راه‌های شیری بین آن‌ها را یال‌های بدون جهت در نظر بگیریم، دانشمندان از شما برنامه‌ای خواسته‌اند که به درخواست‌های زیر پاسخ دهد:

  • $1xyp$: رخ دادن یک پیوندسازی شیری با پارامترهای $(x,y,p)$
  • $2xy$: اندازه‌ی مولفه‌ی همبندی ستاره‌ی شماره‌ی $y$ از کهکشان $x$ چقدر است؟
  • $3$: تعداد کل مولفه‌های همبندی چند تاست؟

ورودی

سطر اول ورودی شامل سه عدد طبیعی $n$، تعداد کهکشان‌ها، $m$ و $q$، تعداد پرسش‌ها، آمده است.($1\leq n \leq 10^5$، $0\leq m \leq 40$ و $1\leq q \leq 4\times 10^5$)

در هر یک از $q$ سطر بعدی یکی از درخواست‌ها با فرمتی که در صورت سوال ظاهر شده قرار دارد.

خروجی

خروجی باید شامل پاسخ به درخواست‌های نوع ۲ و ۳ بر حسب زمان پرسیده شدنشان باشد.

محدودیت‌ها

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

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

ورودی نمونه خروجی نمونه
3 1 10
3
1 1 2 0
3
2 1 0
1 2 3 1
3
2 3 1
1 1 3 0
3
2 2 1
6
4
2
2
3
1
6

ابزار صفحه