naoya_t@hatenablog

いわゆるチラシノウラであります

〈ARC埋め〉600点問題 (ARC 061 E)

ABC/ARC/AGCの500点以下の問題が埋まったので600点問題に進出

ARC 061 E - すぬけ君の地下鉄旅行 / Snuke's Subway Trip (600)

f:id:n4_t:20180718203535p:plain
f:id:n4_t:20180718203545p:plain

  • 都市-都市はweight=0の線を引いて
  • 各都市内の会社別の駅間を結ぶweight=1の線を引く(最初と最後の町ではweight=0)
  • スタート地点=最初の町(i=1)のいずれかの会社の駅
  • ゴール地点=最後の町(i=N)のいずれかの会社の駅

ダイクストラしてみる
→TLE+MLE
https://beta.atcoder.jp/contests/arc061/submissions/2862745
解くべき問題は理解できているみたいなんだけど色々甘かった

  • UnionFindで同じ会社の線で繋がった駅間をくっつけてみる
  • ノード番号を圧縮してダイクストラの計算量を減らしたい

→RE+TLE+MLE
https://beta.atcoder.jp/contests/arc061/submissions/2864886
REが出てるってことはどこかでSEGVか

解説読んだ

解説解と同じ解法だと思うんだけど…
いや違う、
同じ都市内の会社別の駅間を結ぶ線を引くと最悪O(M^2)になって死ぬから「weight=0で改札の外(単一ノード)に出て、weight=1でそこから改札の中に入る」ように引くことでO(2M)に落とす、ってある
なるほど…

1投目のコードをベースに「改札の外」ノードに繋ぐ方式に書き換えてみる
→AC
https://beta.atcoder.jp/contests/arc061/submissions/2865057
嬉しいなるほどだった