+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- فردا تولد حیدریه! دوستان حیدری می‌خواهند برای او تولدی در یک کله‌پزی بگیرند و به همین دلیل به توصیه جعفر گوش کرده‌اند: جعفر توصیه کرده بود که امروز برای بررسی شرایط به کله‌پزی سر بزنند. جعفر و سلطانی که از دوستان با وفای حیدری هستند سوار ماشین شده‌اند تا به کله‌پزی بروند. اما از بد روزگار سلطانی پشت فرمون نشسته و سر یک تقاطع پلیس دیده و به یاد جرم و جنایت‌هایش می‌افتد، به همین دلیل هول شده و تقاطع را اشتباه می‌پیچد. حالا آن‌ها در مرکز شهر گم شده‌اند ولی خوشبختانه جعفر همیشه یک نقشه از مرکز شهر با خودش حمل می‌کند. همه می‌دانیم که مرکز شهر رشت از تعدادی میدان تشکیل شده که در هر میدان یا می‌توان به چپ پیچید یا به راست، و در هر میدان یا می‌توان ساختمان تاریخی شهرداری رشت را دید یا نمی‌توان دید. با این‌که جعفر نقشه را دارد اما مشکل این‌جاست که آن‌ها نمی‌دانند در کدام میدان شهر قرار دارند! جعفر ادعا می‌کند که آن‌ها در میدان $A$ قرار دارند ولی سلطانی می‌گوید در میدان $B$ قرار دارند‌. طبق تجربه ما می‌دانیم همیشه دقیقاً یکی از این دو نفر راست می‌گوید. خوش‌بختانه جعفر نقشه‌اش را از مترو خریده و به همین خاطر روی آن برای هر میدان مشخص شده که آیا می‌توان از آن‌جا ساختمان شهرداری را دید یا نه. حالا آن دو تصمیم گرفته‌اند در شهر حرکت کنند و به هر میدان که می‌رسند از پنجره نگاه کنند که آیا شهرداری را می‌بینند یا نه‌. هم‌چنین با دنبال کردن نقشه یک بار با فرض این‌که ابتدا در میدان $A$ بوده‌اند و یک بار با فرض این‌که در میدان $B$ بوده‌اند و همچنین با توجه به مسیری که تا کنون پیموده‌اند می‌توانند تعیین کنند که آیا در حال حاضر باید بتوانند شهرداری را ببینند یا خیر. به محض این‌که معلوم شود آن‌ها در ابتدا در کدام شهر قرار داشته‌اند آن‌ها خوشحال می‌شوند. با این‌که ما می‌دانیم معمولاً سلطانی اشتباه می‌کند، ولی به آن‌ها بگویید حداقل چند بار باید در میدان های شهر بپیچند تا معلوم شود کدام یک راست می‌گوید، یا تعیین کنید که با این روش نمی‌توان محل آن‌ها را یافت و آن‌ها این سوال را با خود به گور می‌برند. # ورودی در خط اول ورودی ۳ عدد $n$ تعداد میدان‌های مرکز شهر، $A$ شهر مورد نظر جعفر، و $B$ شهر مورد نظر سلطانی با فاصله از هم آمده‌اند. تضمین می‌شود $A$ و $B$ متمایز هستند. سپس در $n$ خط بعدی در خط $i$ام ($i$ از ۰ تا $n$) به ترتیب $l_i$ میدانی که در صورت پیچیدن به چپ در میدان $i$ به آن می‌رسیم و $r_i$ میدانی که در صورت پیچیدن به راست در میدان $i$ به آن می‌رسیم و $t_i$ آمده است.اگر $t_i$ برابر ۱ باشد از میدان $i$ می‌توان ساختمان شهرداری را دید و اگر ۰ باشد نمیتوان. $$2 \le n \le 100\ 000$$ $$0 \le A, B < n$$ # خروجی در تنها خط خروجی کمینه طول مسیر (تعداد پیچیدن های به چپ و راست) را که جعفر و سلطانی باید انجام دهند تا بفهمند حق با کیست چاپ کنید. در صورتی که این کار ممکن نیست تنها عبارت `indistinguishable` را در خروجی چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 3 1 2 1 2 1 0 2 0 0 1 0 ``` ## خروجی نمونه ۱ ``` indistinguishable ``` ## ورودی نمونه ۲ ``` 2 0 1 1 1 1 0 0 0 ``` ## خروجی نمونه ۲ ``` 0 ``` ## ورودی نمونه ۳ ``` 3 1 2 1 2 0 2 0 1 0 1 1 ``` ## خروجی نمونه ۳ ``` 1 ``` ---------- <details class="orange"> <summary> راهنمایی </summary> `dp[i][j]` را برابر جواب سوال وقتی جعفر می‌گوید در راس $i$ هستیم و سلطانی می‌گوید در راس $j$ هستیم قرار می‌دهیم. وقتی $t_i$ و $t_j$ برابر نیستند حاصل دی‌پی برابر ۰ است. با شروع از این پایه ها می‌توان با پیاده کردن الگوریتم $BFS$ این دی‌پی را آپدیت کرد. مشکل این‌جاست که پیچیدگی زمانی این راه حل $n^2$ است، سعی کنید در زمان بهتر راه‌حل را بیابید. </details> <details class="orange"> <summary> راه حل </summary> ابتدا رابطه برابری بین دو راس $v$ و $u$ به این شکل تعریف می‌کنیم که این دو راس از همدیگر قابل تشخیص نیستند. گراف ساده $H$ با $n$ راس را تعریف می‌کنیم به این شکل که اگر دو راس $u$ و $v$ در گراف $H$ به یکدیگر مسیر داشته باشند با هم برابرند. و اگر $u$ و $v$ به هم مسیر نداشته باشند درباره برابر بودن یا نبودن آنها چیزی نمی‌دانیم. در ابتدا فرض می‌کنیم دو راس $A$ و $B$ با هم برابرند. با این فرض، در گراف $H$ باید یک یال بگذاریم. می‌دانیم که با چپ رفتن از دو راس برابر باید به دو راس برابر برسیم. (به همین شکل برای راست رفتن از آن دو راس) پس با فرض برابر بودن $A$ و $B$ به دو نتیجه جدید می‌رسیم. (برابر بودن راس های چپ $A$ و $B$ و همچنین راست آنها) سپس دوباره از نتیجه های جدید، به نتیجه های دیگری می‌رسیم و با هر نتیجه گراف $H$ را آپدیت می‌کنیم. \**لم:** اگر نتیجه جدیدی مانند برابری دو راس $u$ و $v$ کشف کردیم و قبلا می‌دانستیم $u$ و $w$ با هم برابرند، می‌توانیم فرض کنیم نتیجه جدیدمان برابری $v$ و $w$ است و برابری $u$ و $v$ را در نظر نگیریم. با توجه به این لم می‌توانیم به ازای هر مولفه در $H$ تنها یک راس را در نظر بگیریم و بقیه راس ها را حذف کنیم که این کار با داده ساختار $DSU$ به سادگی قابل انجام است. با هر نتیجه، یک راس از گراف $H$ حذف می‌شود. پس ادامه دادن نتایج تا جایی که نتیجه های جدیدی نداشته باشیم، در زمان $O(n)$ امکان‌پذیر است. می‌دانیم که برابر بودن دو راس $u$ و $v$ که از یکی میدان اصلی رشت معلوم است و از دیگری معلوم نیست، تناقض است. پس اگر در نتایجمان به چنین تناقضی رسیدیم، طبیعتاً متوجه می‌شویم که فرض برابر بودن $A$ و $B$ (راس‌های شروع) درست نیست. پس این دو راس از یک‌دیگر قابل تشخیصند. حال می‌خواهیم در کوتاه ترین زمان آنها را از هم تشخیص بدهیم. بدیهی است که این عمل معادل است با اینکه $A$ و $B$ را برابر بگیریم و در کوتاه‌ترین زمان (یعنی مثلا فرض کنید بین دو نتیجه یال جهت‌دار می‌گذاریم) به تناقض برسیم. این کار را می‌توانیم با الگوریتمی شبیه $BFS$ و ساختن نتیجه های جدید از نتیجه های قبلی انجام دهیم، و در هر مرحله که ۲ راس را برابر می‌کنیم در $DSU$ی تعریف شده آن دو را مرج کنیم. </details>

حل سؤال در بانک سؤالات