問題一覧 > 通常問題

No.2316 Freight Train

レベル : / AI推定難易度 : 353 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 194
作問者 : 👑 amentorimaru / テスター : tatyam cleantted
お気に入りにしたユーザー ProblemId : 9210 / 自分の提出
問題文最終更新日: 2023-05-26 12:26:40
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 390 (順位表) の他の問題:

Problem Statement

$N$ Etowanye-kun are playing a game of trains, walking together in several groups, each lined up in a single row. How cute!


The $i$-th Etowanye-kun is behind the $P_i$-th Etowanye-kun. If $P_i=-1$, he is at the front.

You are given $Q$ queries; determine whether the $A_i$-th Etowanye-kun and the $B_i$-th Etowanye-kun are in the same train row.

Input

$N \ Q$
$P_1 \ P_2 \ \dots \ P_N$
$A_1 \ B_1$
$A_2 \ B_2$
$\vdots$
$A_Q \ B_Q$
  • All inputs are integers.
  • $1 \le N,Q \le 2\times 10^5$
  • $1 \le A_i,B_i \le N$
  • $1 \le P_i \le N$ or $P_i=-1$
  • $P_i \ne P_j$ for $i \ne j$ with $P_i \ne -1, P_j \ne -1$
  • $P_i \ne i$
  • Every train has an Etowanye-kun at its front.

Output

Print Yes if they are in the same row, and No otherwise.

Sample

Sample 1
Input
5 3
-1 4 1 -1 3
1 5
4 2
3 4
Output
Yes
Yes
No

The first row consists of Etowanye-kun $1,3,5$ from the front, and

the second row consists of Etowanye-kun $4,2$ from the front.

In the $1$-st query, both are in the first row, so print Yes.

In the $2$-nd query, both are in the second row, so print Yes.

In the $3$-rd query, they are in different rows, so print No.

Sample 2
Input
5 3
-1 -1 -1 -1 -1
1 2
2 3
4 4
Output
No
No
Yes

Every Etowanye-kun is cute even when walking alone.

A query may contain the same value twice.

Sample 3
Input
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
Output
No
Yes
Yes
No
Yes
Yes
No
No
No
No
No
Yes
No
No
No
No
No
Yes
No
Yes

Note that large $N,Q$ may appear.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。