hamayanhamayan https://blog.hatena.ne.jp/hamayanhamayan/ はまやんはまやんはまやん https://blog.hamayanhamayan.com/ 競技プログラミング https://codeforces.com/contest/1276/problem/B 解説 https://codeforces.com/contest/1276/submission/66871631 あるx,yについて全ての経路でa,bを通るということは、 頂点a,bを抜くとxからyに到達不可能になるということ。 よって、頂点a,bを抜いた状態で考えてみよう。 頂点a,bを抜いて、unionfindで連結成分をまとめよう。 この連結成分毎に頂点aにつながっているか、bにつながっているか、どちらにもつながっているかを判定する。 求めたい経路はx→a→b→yであるため、頂点aにのみつなが… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fblog.hamayanhamayan.com%2Fentry%2F2019%2F12%2F14%2F225805" title="Two Fairs [Codeforces Round #606 (Div. 1, based on Technocup 2020 Elimination Round 4) B] - はまやんはまやんはまやん" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2019-12-14 22:58:05 rich https://blog.hamayanhamayan.com/entry/2019/12/14/225805 1.0 100%