蟻本の練習問題埋め2-4(2)
Union-Find
POJ 2236 - Wireless Network
http://poj.org/problem?id=2236
問題
ネットワーク上にN個のコンピュータがあるが、全て壊れてしまった。
コンピュータは平面座標上に位置するとみなすことが出来る。
コンピュータpが復旧したというメッセージと、コンピュータpとqが通信できるかというメッセージが与えられる。
後者のメッセージに対して、通信できるならSUCCESS、出来無いならFAILを出力せよ。
ただし、距離がd以内の復旧しているコンピュータ同士は通信でき、aとb、bとcが通信できるとき、aとcも通信できる。
制約
N<=1001
入力は最大で3*10^5行
解法
通信ができるコンピュータは同じ集合に属する、というようなUnion-Findを作っていく。
コンピュータpが復旧したとき、今までに復旧している全てのコンピュータに対して距離がd以内か判定し、d以内なら同じ集合とする。
POJ 1703 - Find them, Catch them
http://poj.org/problem?id=1703
問題
ある市には２つのギャングが存在する。
この市の中で、少なくとも１人は一方のギャングに属し、同様にもう一方のギャングにも少なくとも1人は属している。
全体でN人がギャングに属しており、M個のメッセージがある。
各メッセージは
- aとbは違うギャングに属する
- aとbが同じギャングに属するか違うギャングに属するか判定せよ
という２つのタイプがある。
後者のタイプのメッセージそれぞれに対し、
- 同じなら"In the same gang."
- 違うなら"In different gangs."
- 分からないなら"Not sure yet."
を出力せよ。
制約
テストケースの数<=20
N,M<=10^5
AOJ 2170 - Marked Ancestor
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2170
問題
要素数Nの木を考える。各ノードは1〜Nの番号がついており、番号1のノードは常に根である。
オペレーションとして、以下の２つがある。
- ノードvをマークする
- ノードvの祖先のうち最も近いマークされたノードの番号を出力する
オペレーションがQ個与えられるので、出力されるべき数字の合計を求めよ。
制約
N,Q<=10^5
解法
解説参照。
ざっくり言うと、クエリを全部見た後、クエリを後ろから処理する。
このときUnionFindを使う。
各集合は、その集合に属するノードに対する答えとなる値を持つ。
後ろから見ることによって、答えとなる値が違うようなノードがどんどんまとまっていくというのがポイント。
難しい・・・
