library-checker-problems
library-checker-problems copied to clipboard
yosupo06
[問題案] Persistent Unionfind
(任意) 問題ID: {persistent_unionfind} 問題名: {Persistent Unionfind}
(任意) 想定アルゴリズム: {永続 Unionfind} (任意) 参考資料: {https://ei1333.github.io/luzhiled/snippets/structure/union-find.html}
問題概要
$N$ 頂点 $0 $ 辺のグラフに $Q$ 個のクエリが飛んでくるので、処理してください。
なお、それぞれのクエリには $1$ から $Q$ までの異なる番号 $k$ がついているものとし、最初の状態のグラフ ($N$ 頂点 $0 $ 辺のグラフ) は 「$0 $ 番目のクエリを処理した直後の時点のグラフ」と定義します。
- $k_i$ 番目のクエリを処理した直後の時点でできているグラフに対して、辺 $(u_i, v_i)$ を追加し (すでに辺が存在するならば無視される)、それを処理し終えた直後のグラフを「$i$ 番目のクエリを処理した直後の時点のグラフ」と定義する。
- $k_i$ 番目のクエリを処理した直後の時点でできているグラフに対して、頂点 $u_i$ と $v_i$ が連結であるかどうかを答える。
入力
$N$ $Q$
$t_1$ $k_1$ $u_1$ $v_1$
$\vdots$
$t_Q$ $k_Q$ $u_Q$ $v_Q$
制約
- $1 \leq N \leq 100,000$
- $1 \leq Q \leq 100,000$
- $t_i \in \left{ 1, 2 \right}$
- $0 \leq k_i < i$
- $0 \leq u_i, v_i < N$
検討事項
https://twitter.com/kimiyuki_u/status/1251170386881855489 を見たので
- 部分永続？完全永続？
- 1 番目のクエリにおいて最新版のみ更新対象にするかどうかの問題
- TL / ML (あるいは制約) は？
- 完全永続なら重そうですね
- 問題文
- どうすると伝わりやすい文章になるのかが難しそうです
k_i は、(k_i = 0) or (k_i 番目のクエリが 1 番目 (unite) の処理) であることを保証したほうがよさそうだが、問題文に書くのが大変そうな気がする？
https://judge.yosupo.jp/problem/persistent_queue 基本的にこれを参考にしていただければと思います
- 最初の要素は-1番目で(ちょっと不自然な感じもしますが、0-indexed ジャッジなので、まあ…)
k_i は、(k_i = 0) or (k_i 番目のクエリが 1 番目 (unite) の処理) であることを保証したほうがよさそうだが、問題文に書くのが大変そうな気がする？
これはあってもなくてもいいと思います 書くならこの通りに書けば大丈夫かと
すみません、インデックスの件は https://judge.yosupo.jp/problem/unionfind に合わせて 1-indexed にしてしまっていました・・・ (Persistent Queue の方に合わせます)
とりあえず作業します (また相談するかもしれません)
There is a report that https://judge.yosupo.jp/submission/22415 should be failed with the following case
3 3
0 -1 0 1
0 -1 1 2
1 1 0 1
