ARC 164

Fri, May 2, 2025

A. Ternary Decomposition

https://atcoder.jp/contests/arc164/tasks/arc164_a

B. Switching Travel

https://atcoder.jp/contests/arc164/tasks/arc164_b

2日位かけて AC。

直線の移動では移動元の色と現在いる場所の色が一緒で戻ることはできないため、経路が存在するとすれば閉路を形成する必要がある。移動するたびに移動元の色が変わるため閉路の経路は以下の2通りのどちらかになる必要がある。

+--B-W-W-B--+       +--W-B-B-W--+
W           W       B           B
|           |       |           |
B           B       W           W
+----...----+       +----...----+

まず、色の異なる2点をつなぐ辺を全て連結させた後、同じ色の同士の頂点を結ぶ辺を加えたときに閉路になるかどうかを調べる。閉路が存在すれば Yes を出力し、存在しなければ No を出力する。

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    cin >> N >> M;

    vector<pair<int, int>> es;

    rep(i, M) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        es.emplace_back(a, b);
    }

    vint col(N);
    rep(i, N) cin >> col[i];

    vector<pair<int, int>> same_col;

    dsu uf(N);
    for (auto [u, v] : es) {
        if (col[u] != col[v])
            uf.merge(u, v);
        else
            same_col.push_back({u, v});
    }

    int ok = 0;
    for (auto [u, v] : same_col) {
        if (uf.same(u, v))
            ok = 1;
    }
    yesno(ok);
}