問題一覧 > 通常問題

No.2316 Freight Train

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 189
作問者 : 👑 amentorimaruamentorimaru / テスター : tatyamtatyam cleanttedcleantted
1 ProblemId : 9210 / 出題時の順位表 / 自分の提出
問題文最終更新日: 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もしくは右上の雲マークをクリックしてアカウントを作成してください。