Quiz
https://atcoder.jp/contests/arc025/tasks/arc025_3
Submit
https://atcoder.jp/contests/arc025/submissions/4186238
解き方と計算量
- ゴールを固定する
- ゴールから各ノードまでの距離をDijkstraで求める O( (N+M)logN )
- 距離をソート O(NlogN)
- (a) 亀の距離を固定したとき、ウサギの距離のしきい値も決まる
- (b) upper_bound (二分探索)でウサギの取り得るノードの数も決まる
- (a), (b) 合わせてO(NlogN)
- ゴールも総当たりするので、全体ではO(N2 log N)
- (N≒Mとした)
計算時間
- 2500 x 2500 x log(2500) = 2 * 107
- 実行時間制限 7秒
- 私の提出では1秒ちょいかかるものもあった
- 107はギリギリ通るようだ
テストケース1の場合 (0-index)