大手前プロコン 2019：G - 空をかけるピ太郎 (Pitaro, who Leaps through Air)

問題
解法
解答

問題

https://atcoder.jp/contests/otemae2019/tasks/otemae2019_g

解法

N が大きいので，P, Q, R, S, A_i, B_i, C_i, D_i を x, y 座標に分けて座標圧縮をする．また，上下・左右方向にワープ可能な領域をそれぞれ累積和で求めておく．このとき，別のワープ可能な領域が隣り合っているとき，隣り合っているところをまたぐ際にコストが生じるので，累積和を求める段階で 0 を検出したらコストがかかると判定する必要がある．これで各マス間の移動のコストが求まったので，二次元平面上でダイクストラ法を使って (P, Q) から (R, S) の最短距離を求めればよい．O(M^2 * logM)．