No.2316 Freight Train
タグ : / 解いたユーザー数 194
作問者 : 👑
amentorimaru
/ テスター :
tatyam
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もしくは右上の雲マークをクリックしてアカウントを作成してください。