No.2319 Friends+
タグ : / 解いたユーザー数 82
作問者 : 👑
amentorimaru
/ テスター :
tatyam
Problem Statement
In a certain virtual space, there are $N$ Etowanyu-kun numbered $1,2,\dots,N$, and $N$ worlds numbered $1,2,\dots,N$. Initially, Etowanyu-kun $i$ is in world $P_i$.
In addition, there are $M$ bidirectional friend relationships among the Etowanyu-kun: Etowanyu-kun $A_i$ and Etowanyu-kun $B_i$ are friends with each other.
From now on, the Etowanyu-kun will travel between worlds using the join command described below. It's cute how they wander around.
Join command
When Etowanyu-kun $X$ uses the join command on Etowanyu-kun $Y$, the following happens.
- If the following $2$ conditions are both satisfied, the join command succeeds, and Etowanyu-kun $X$ moves to the world where Etowanyu-kun $Y$ is.
- Etowanyu-kun $X$ and Etowanyu-kun $Y$ are in different worlds.
- At least one friend of Etowanyu-kun $X$ is in the world where Etowanyu-kun $Y$ is.
- Otherwise, the join command fails, and Etowanyu-kun $X$ stays where it is.
You are given $Q$ join commands performed by the Etowanyu-kun, in order. The $i$-th command is that Etowanyu-kun $X_i$ joins Etowanyu-kun $Y_i$. Determine whether each command succeeds or fails.
Input
$N \ M$ $P_1 \ P_2 \ \dots P_N$ $A_1 \ B_1$ $A_2 \ B_2$ $\vdots$ $A_M \ B_M$ $Q$ $X_1 \ Y_1$ $X_2 \ Y_2$ $\vdots$ $X_Q \ Y_Q$
- All input values are integers.
- $1 \le N \le 2 \times 10^4$
- $0 \le M \le \min(2 \times 10^5, N(N+1)/2)$
- $1 \le Q \le 2 \times 10^5$
- $1 \le A_i,B_i,X_i,Y_i,P_i \le N$
- For $i \ne j$, $(A_i,B_i) \ne (A_j,B_j)$ and $(A_i,B_i) \ne (B_j,A_j)$.
Output
Print $Q$ lines. On the $i$-th line, print Yes if the $i$-th join command succeeds, and No if it fails.
Sample
Sample 1
Input
4 2 1 2 2 3 1 2 1 4 5 1 3 1 4 2 4 1 4 1 3
Output
Yes Yes Yes No No
Initially, Etowanyu-kun $1, 2, 3, 4$ are in worlds $1, 2, 2, 3$, respectively. Etowanyu-kun $1$ and Etowanyu-kun $2$ are friends with each other, and so are Etowanyu-kun $1$ and Etowanyu-kun $4$.
In the $1$-st command, Etowanyu-kun $1$ and Etowanyu-kun $3$ are not friends, but Etowanyu-kun $2$, who is in the same world as Etowanyu-kun $3$, is a friend of Etowanyu-kun $1$, so the join succeeds. Print Yes; the worlds of all the Etowanyu-kun become $2,2,2,3$, respectively.
In the $2$-nd command, Etowanyu-kun $1$ and Etowanyu-kun $4$ are friends, so the join succeeds. Print Yes; the worlds of all the Etowanyu-kun become $3,2,2,3$, respectively.
In the $3$-rd command, Etowanyu-kun $2$ and Etowanyu-kun $4$ are not friends, but Etowanyu-kun $1$, who is in the same world as Etowanyu-kun $4$, is a friend of Etowanyu-kun $2$, so the join succeeds. Print Yes; the worlds of all the Etowanyu-kun become $3,3,2,3$, respectively.
In the $4$-th command, Etowanyu-kun $1$ and Etowanyu-kun $4$ are friends, but they are in the same world, so the join fails. Print No.
In the $5$-th command, there are no friends of Etowanyu-kun $1$ in the world where Etowanyu-kun $3$ is, so the join fails. Print No.
Sample 2
Input
1 1 1 1 1 1 1 1
Output
No
In this virtual space, it seems possible to be friends with oneself.
Etowanyu-kun $1$ tries to join Etowanyu-kun $1$, but the join fails because they are in the same world.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。