No.2316 Freight Train
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 186
作問者 : 👑 amentorimaru / テスター : tatyam cleantted
タグ : / 解いたユーザー数 186
作問者 : 👑 amentorimaru / テスター : tatyam cleantted
問題文最終更新日: 2023-05-26 12:26:40
問題文
$N$ 匹のエトワーニュくんが何組かで一列に並んで一緒に歩く電車ごっこをしています。かわいいですね。
$i$ 匹目のエトワーニュくんは $P_i$ 匹目のエトワーニュくんの後ろにいます。$P_i=-1$ の場合は先頭にいます。
$Q$ 個のクエリが与えられますので $A_i$ 匹目のエトワーニュくんと $B_i$ 匹目のエトワーニュくんが同じ電車の列にいるか判定してください。
入力
$N \ Q$ $P_1 \ P_2 \ \dots \ P_N$ $A_1 \ B_1$ $A_2 \ B_2$ $\vdots$ $A_Q \ B_Q$
- 入力は全て整数
- $1 \le N,Q \le 2\times 10^5$
- $1 \le A_i,B_i \le N$
- $1 \le P_i \le N$ または $P_i=-1$
- $P_i \ne -1, P_j \ne -1$ である $i \ne j$ について $P_i \ne P_j$
- $P_i \ne i$
- 全ての電車には先頭となるエトワーニュくんがいる
出力
同じ列にいる場合は Yes
、そうでない場合は No
を出力してください。
サンプル
サンプル1
入力
5 3 -1 4 1 -1 3 1 5 4 2 3 4
出力
Yes Yes No
一列目は前から $1,3,5$ のエトワーニュくんが並んでおり
二列目は前から $4,2$ のエトワーニュくんが並んでいます。
$1$ 番目のクエリはどちらも一列目にいるため Yes
を出力します。
$2$ 番目のクエリはどちらも二列目にいるため Yes
を出力します。
$3$ 番目のクエリは違う列にいるため No
を出力します。
サンプル2
入力
5 3 -1 -1 -1 -1 -1 1 2 2 3 4 4
出力
No No Yes
全てのエトワーニュくんは一匹だけで歩いてもかわいいです。
クエリに同じ値が出てくる場合もあります。
サンプル3
入力
20 20 7 20 11 -1 12 -1 -1 17 15 6 16 -1 9 4 3 5 14 19 -1 1 7 11 16 15 20 7 7 12 11 16 20 20 19 5 19 1 10 20 14 9 11 19 11 15 2 18 12 2 1 12 15 4 19 10 14 4 18 2 10 10
出力
No Yes Yes No Yes Yes No No No No No Yes No No No No No Yes No Yes
大きな $N,Q$ が出てくることに注意してください。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。