🌳
[ABC040 D] 道路の老朽化対策について
削除するために最初から作るのだが頂点に対応する辺の選択が難しい問題。
考え方
クエリ毎に無効な道路を毎回削除しても解けるが遅いので、期限の新しい順に有効な道路を作っていく。
例1のシミュレーション
見やすくするため辺の情報とクエリを製造年と期限の降順にしておく。
| 辺 | 製造年 |
|---|---|
| 2-3 | 2004 |
| 4-5 | 2001 |
| 1-2 | 2000 |
| 3-4 | 1999 |
| 都市 | 期限 | |
|---|---|---|
| Q1 | 1 | 2000 |
| Q2 | 1 | 1999 |
| Q3 | 3 | 1995 |
そして問題文の通りに森 1-2-3-4-5 から「毎回、期限切れの辺を削除する」とすれば、
| 都市 | 期限 | 期限 >= 製造年 な辺 | 素集合森 | 都市の木の大きさ | |
|---|---|---|---|---|---|
| Q1 | 1 | 2000 | 1-2 3-4 | 1 2-3 4-5 | 1 |
| Q2 | 1 | 1999 | 3-4 | 1-2-3 4-5 | 3 |
| Q3 | 3 | 1995 | 1-2-3-4-5 | 5 |
となるのだが、削除ができないため反転し「新しい辺から作っていく」と、
| 都市 | 期限 | 期限 < 製造年 な辺 | 素集合森 | 都市の木の大きさ | |
|---|---|---|---|---|---|
| Q1 | 1 | 2000 | 2-3 4-5 | 1 2-3 4-5 | 1 |
| Q2 | 1 | 1999 | 1-2 | 1-2-3 4-5 | 3 |
| Q3 | 3 | 1995 | 3-4 | 1-2-3-4-5 | 5 |
になる。新しい辺から作っていく場合は、クエリを期限の降順としておく。(例1ではもとから降順になっている)
コード (AC)
N, M = gets.split.collect(&:to_i) # => [5, 4]
ABY = M.times.collect { gets.split.collect(&:to_i) } # => [[1, 2, 2000], [2, 3, 2004], [3, 4, 1999], [4, 5, 2001]]
Q = gets.to_i # => 3
VW = Q.times.collect { gets.split.collect(&:to_i) } # => [[1, 2000], [1, 1999], [3, 1995]]
# 辺を製造年の降順にする
edges = ABY.sort_by { |a, b, birth| -birth } # => [[2, 3, 2004], [4, 5, 2001], [1, 2, 2000], [3, 4, 1999]]
# 最後にクエリ順にするためインデックスを混ぜて期限の降順にする
queries = VW.collect.with_index { |(town, limit), i| [town, limit, i] } # => [[1, 2000, 0], [1, 1999, 1], [3, 1995, 2]]
queries = queries.sort_by { |town, limit, i| -limit } # => [[1, 2000, 0], [1, 1999, 1], [3, 1995, 2]]
ans = []
ds = DisjointSet.new
queries.each do |town, limit, i|
# 期限が切れていない辺を作る
while (*edge, birth = edges.first) && birth > limit
ds.unite(*edge)
edges.shift
end
# そのうえで住んでいる都市から行ける都市の数(連結成分の大きさ)を得る
ans[i] = ds.size(town)
end
ans # => [1, 3, 5]
puts ans
Discussion