オンサイトで未確認

ukuku09の活動記録。

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

一昨日のABC埋め。

 

問題文

abc040.contest.atcoder.jp

解法

$y_i$ の降順に全域木を作っていくと、i 本目の道路を使う直前の状態というのは、 $y_i$ 年以前の道路を含まない部分グラフとなっている。結局、初めて $w_j$ 以下となる $y_i$ の道路を使う直前の部分グラフの大きさが、各クエリの答えとなる。クエリを先読みして $w_j$ でソートしておくと、Kruskal 法で全域木を作る過程でうまく答えを求められる。

全域木となった時点で、任意の異なる2都市間を移動することができるようになるので、その他の道路については考えなくても良い。

 

余談

これICPC直前のABCで、大学でチームメンバーと一緒に出た(もちろん個人戦)記憶があるなぁ。あの時はこれ解けなかったけど。