ABC254 G - Elevators (600)
コンテスト中の考察
逆方向に進む意味は無い
同じビルのエレベータで重複している部分があるならそれらを合わせた新しい1つのエレベーターとして見做すと便利
各クエリでスタートとゴールで同じビル内で近づける移動があるならできるだけする
スタートがゴール以下の階になるように必要ならswapする
ここまでで階数が一致した場合、
同じビルなら0
違うビルなら1
エレベータの内貪欲に移動していく
解説の解法
何回か移動した後の移動先をダブリングで求める
座標圧縮を事前に行う
エレベータの階だけではなくクエリの階も含めておくと便利
ダブリングの結果から必要な移動階数を求める方法が分からなかったので解説で$ \mathcal{O}(\log M)の所、$ \mathcal{O}(\log^2 M)で実装した
上限回数移動しても到着していないなら不可能と言うことなので-1を返す
ダブリングの結果のビルからクエリのゴールのビルへの移動の1を答えに足し忘れないよう注意が必要
この実装だと$ \mathcal{O}((M+Q \log M) \log M)