المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی انتخاب تیم:دوره ی ۱۷:سوال ۸

The Agency

یک سازمان اطلاعاتی $n$ عضو دارد، با شماره‌های ۱ تا $n$. ساختار تشکیلاتی این سازمان به شکل یک درخت ریشه‌دار است که عضو شماره‌ی ۱ رئیس سازمان و ریشه‌ی این درخت می‌باشد.

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

سیستم به این صورت است که هر گاه یکی از اعضا عطسه کرد، رویه‌ی خود و همه‌ی زیردستانش را تغییر می‌دهد(توجه کنید که زیردست یک نفر، زیردست او هم هست). منظور از تغییر رویه‌ی یک نفر، این است که اگر قبلا اطلاعات درست می‌داده، از این به بعد اطلاعات غلط می‌دهد و برعکس. در ابتدا همه راست‌گو هستند.

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

برنامه‌ای بنویسید که:

  • ساختار تشکیلاتی سازمان، آمار عطسه‌های اعضا و اطلاعات دریافتی از اعضا را از ورودی بخواند.
  • درستی یا نادرستی هر یک از اطلاعات به‌دست آمده را بررسی کند.
  • نتیجه (درستی یا نادرستی اطلاعات) را در خروجی بنویسد.

ورودی

  • در سطر اول ورودی، دو عدد $n$(تعداد اعضا) و $m$(تعداد عطسه‌ها و پرسش‌ها) قرار دارد.($1\leq n,m \leq 10^5$)
  • در $n$ سطر بعد اطلاعات مربوط به ساختار تشکیلاتی سازمان به این صورت آمده است که در سطر $i$ام از این $n$ سطر، ابتدا تعداد زیردستان مستقیم عضو شماره‌ی $i$ و سپس شماره‌ی زیردستان مستقیم آمده است. این اعداد با فاصله از هم جدا شده‌اند.
  • پس از آن $m$ سطر آمده که در هر سطر دو عدد $a$ و $b$ با یک فاصله از هم نوشته شده است. اگر $a=0$، یعنی عضو شماره‌ی $b$ عطسه کرده و اگر $a=1$، یعنی اطلاعاتی از عضو شماره‌ی $b$ پرسیده شده است.

خروجی

در سطر $i$ام خروجی، پاسخ پرسش $i$ام ورودی را بنویسید(یعنی $i$امین سطری که در آن $a=1$ است). اگر اطلاعاتی که به عنوان پاسخ داده شده، غلط بوده ۱ و در غیر این صورت ۰ چاپ کنید.

توجه داشته باشید که هیچ فاصله‌ای در فایل خروجی وجود نداشته باشد.

محدودیت‌ها

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

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

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

ابزار صفحه