AtCoder Beginner Contest 040 D - 道路の老朽化対策について

ABC ABC-D AtCoder Union Find 競技プログラミング

問題概要

(リンク)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) ) ) ？ (わからん) (間に合うということはわかる)