ぱらつり記

No description

ARC#032

かなしい

久々のARCってことで参加しましたがA問題に真正面から突っ込んでB問題でTLE地獄で死にました。

いつもの表です

提出時刻 結果 AC数
21:00:00 開始 --
21:34:55 TLE 18/22
21:56:10 TLE 17/22
22:17:03 TLE 17/22
22:30:00 終了 --
23:13:31 TLE 17/22
23:31:33 AC 22/22

問題を見て5分くらいしてから「繋がった交差点を1つの島として 島の総数 - 1 を求めればいい」という結論にたどり着き、せこせこ実装して提出しましたが、見事に終わりの方のテストケースでTLE。

訪れていない交差点 をListで管理していたのが悪かったようです。 C#の正答コードを参考に幅優先から深さ優先探索に書き直してようやくAC。

Listのコストを思い知りました。
これを機に配列でうまく組めるようになっていきたいです。

素直にUnionFind使えよって突っ込みは受け付けてます。