考察
component 間距離の最小値は、異なる component に属する頂点 pair の Manhattan 距離の最小値と同じなので、候補を全頂点 pair として持てる。
type 2 で最小距離 k の全 pair を同時に union すれば、同じ k の辺による推移的な連結も一回の query 内で正しく反映される。
採用する候補: 追加済み全頂点 pair を距離付き min-heap に入れ、DSU で既に同 component の stale pair を遅延削除する
各 pair は一度 push/pop される。
棄却する候補: type 2 ごとに現在の component pair ごとの距離を全頂点 pair から再計算する
最大約3000頂点の二乗走査を最大1500 queryで繰り返し、component merge後も同じ距離を何度も評価する。
初期 N 頂点の全 unordered pair を heap に入れる。type 1 では新頂点と既存全頂点の pair を追加する。type 2 は連結済み pair を pop し、heap が空なら -1、そうでなければ最小 key k を固定して key=k の pair を全て pop・unionして k を出力する。type 3 は DSU.same を返す。
典型の発動条件
priority queue の遅延削除
発動条件: 候補の有効性が DSU の merge で失われるが、失効後に復活しないとき。
heap top を使う直前に same を確認し、stale pair を捨てる。
DSU
発動条件: 辺追加だけで component が併合され、connectivity query があるとき。
最小距離 group の全 pair を union し、type 3 をほぼ定数時間で答える。
全 pair の offline 候補化
発動条件: 総頂点数が約3000で、各 pair の固定距離を一度だけ計算すればよいとき。
初期および追加時に unordered pair を heap へ一度登録する。
問題固有の要素
component 距離を明示管理せず、頂点 pair の supersets を heap に保持して DSU で現在有効な最小だけを抽出する。
別の問題へ持ち帰る視点: 集合間最小値が要素 pair の最小で、集合がmergeしかしないなら、全 pair候補+単調なlazy invalidationを検討する。
正当性
heap 上位が既に連結ならその pair は将来も連結のままなので、永久に捨ててよい。この単調性で stale entry の再構築が不要になる。 最初の有効 pair を union した後も heap key が k の entry をすべて処理する必要がある。途中で component が変化しても、距離 k の全辺を加えた連結成分が問題文の同時 merge と一致する。 頂点追加時に過去頂点との pair だけを追加し、type 2 では最初の非連結 pair の距離 k と同距離の全 pair を union する。各 pair は一度 push/pop される。
実装上の注意
- type 2 の開始前に k 未満を含む連結済み top をすべて除く。同距離 k は有効・無効を問わず全て pop し、距離は 64 bit、総 pair 数分のmemoryを確保する。
復習の核
- 既に全連結、同じ最小距離がchain状に並ぶ、同距離pairの一部がstale、新頂点が最小距離を更新する例を愚直component距離計算と比較する。
計算量と制約
時間
O(P² log P+Q α(P))、Pは全追加後の頂点数。各pairは一回push/popされる。
空間
O(P²+Q)。
制約との対応
公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 2\leq N\leq 1500; 1\leq Q\leq 1500; 0\leq x_i,y_i\leq 10^9; For queries of type 1, 0\leq a,b\leq 10^9.; For queries of type 3, let n be the number of vertices in G just before processing that query, then 1\leq u\lt v\leq n.; All input values are integers.
出典