Persistent UnionFind

AC一覧

Problem Statement
問題文

Let $G_{-1}$ be the graph which consists of $N$ vertices and no edges. Process $Q$ queries in order. The $i$-th query is given with the following format:

  • 0 $k_{i}$ $u_{i}$ $v_{i}$: Let $G_{i}$ be the graph, which is made by adding an edge $\left( u, v \right)$ to $G_{k_{i}}$.
  • 1 $k_{i}$ $u_{i}$ $v_{i}$: If vertices $u, v$ in $G_{k_{i}}$ are connected, print $1$. Otherwise, print $0$.

$G_{-1}$ を、$N$ 個の頂点からなる、辺がひとつも存在しないグラフとします。$Q$ 個のクエリを処理してください。$i$ 個目のクエリは以下の形式で与えられます。

  • 0 $k_{i}$ $u_{i}$ $v_{i}$: $G_{k_{i}}$ に辺 $\left( u_{i}, v_{i} \right)$ を追加したグラフを $G_{i}$ とする。
  • 1 $k_{i}$ $u_{i}$ $v_{i}$: グラフ $G_{k_{i}}$ において $u_{i}, v_{i}$ が連結ならば $1$ を、そうでなければ $0$ を出力する。

Constraints
制約

Input
入力

$N$ $Q$
$t_0$ $k_0$ $u_0$ $v_0$
$\vdots$
$t_{Q-1}$ $k_{Q-1}$ $u_{Q-1}$ $v_{Q-1}$

Sample
サンプル

# 1

5 12
0 -1 0 1
0 0 0 2
1 -1 0 1
1 0 0 1
1 1 0 1
0 1 3 4
0 1 2 3
1 5 1 4
0 5 2 3
1 8 1 4
0 6 3 4
1 10 1 4
0
1
1
0
1
1

Forum


Timelimit: 5 secs

Before submitting, please confirm terms and conditions