2019年5月8日水曜日

JOI2011 本選 E - JOI 国のお祭り事情

JOI2011 本選 E - JOI 国のお祭り事情

ダイクストラ法で、各頂点vVv \in Vからお祭りが開催される頂点への最短距離w(v)w(v)を求めておく。次に、空のグラフからスタートして、w(v)w(v)が大きい頂点から順に与えられたグラフを復元していく。このとき、a,bVa, b \in Vがつながった瞬間のwwの値が、パスaba - bのお祭りからの最長距離である。構築の際に部分永続Union-Findを使っておけば、クエリ(Si,Ti)(S_i, T_i)に対してはSiTiS_i - T_iがいつつながったかを二分探索で求められる。

最初、Dijkstra → Kruskal → ダブリングLCAの拡張っぽいやつでなんとかなるかもなどと妄想していたらそれが想定解だったらしい。実際には、Kruskalの正当性について考えているあいだに部分永続Union-Findでいけそうと思ったため、そちらを実装した。1 想定解のほうもそのうちやりたい。

ところで、多始点の場合、ダイクストラ法のキューのサイズはE|E|が上限ではないことに気づいた。始点の数をkkとするとき、k+Ek + |E|あれば安全なはず。始点の数が不確定な時はV+E|V|+|E|で良さそう。


  1. drkenさんのリストに載っていたから手を付けたので、純粋に思いついたというわけではない。 ↩︎