AtCoder Beginner Contest 040 D - 道路の老朽化対策について
問題概要
(リンク)http://abc040.contest.atcoder.jp/tasks/abc040_d
- y_i年に作られた道は都市a_iと都市b_iを結ぶ
- 住民jはv_jに住んでいてw_j以前に作られた道を通りたくない
- 全ての住人が移動できる都市の数を求める
解法
- UnionFindを使う
- 少し拡張してUnionの個数を数えられるようにする
- 全ての住人に対して1からUnionFindを使うとTLEとなる
- v_jが降順となるようにクエリを並べ替える
- w_jが降順となるように道を並べ替える
- こうすることで重複した処理を行わずにすむ
- O(max(N log N, Q log Q, Q+M log α(N) ) ) ? (わからん) (間に合うということはわかる)