提出 #46031530

---

ソースコード 拡げる

#include <bits/stdc++.h>

using i64 = long long;

struct TwoSat {
    int n;
    std::vector<std::vector<int>> e;
    std::vector<bool> ans;
    TwoSat(int n) : n(n), e(2 * n), ans(n) {}
    void addClause(int u, bool f, int v, bool g) {
        e[2 * u + !f].push_back(2 * v + g);
        e[2 * v + !g].push_back(2 * u + f);
    }
    bool satisfiable() {
        std::vector<int> id(2 * n, -1), dfn(2 * n, -1), low(2 * n, -1);
        std::vector<int> stk;
        int now = 0, cnt = 0;
        std::function<void(int)> tarjan = [&](int u) {
            stk.push_back(u);
            dfn[u] = low[u] = now++;
            for (auto v : e[u]) {
                if (dfn[v] == -1) {
                    tarjan(v);
                    low[u] = std::min(low[u], low[v]);
                } else if (id[v] == -1) {
                    low[u] = std::min(low[u], dfn[v]);
                }
            }
            if (dfn[u] == low[u]) {
                int v;
                do {
                    v = stk.back();
                    stk.pop_back();
                    id[v] = cnt;
                } while (v != u);
                ++cnt;
            }
        };
        for (int i = 0; i < 2 * n; ++i) if (dfn[i] == -1) tarjan(i);
        for (int i = 0; i < n; ++i) {
            if (id[2 * i] == id[2 * i + 1]) return false;
            ans[i] = id[2 * i] > id[2 * i + 1];
        }
        return true;
    }
    std::vector<bool> answer() { return ans; }
};


std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());

void solve() {
    int N;
    std::cin >> N;
    
    std::vector<std::vector<int>> adj(N);
    for (int i = 0; i < 3 * N / 2; i++) {
        int A, B;
        std::cin >> A >> B;
        A--, B--;
        adj[A].push_back(B);
        adj[B].push_back(A);
    }
    
    std::vector<int> ans(N);
    
    while (true) {
        for (int i = 0; i < N; i++) {
            ans[i] = rng() % 2;
        }
        
        TwoSat ts(N);
        for (int i = 0; i < N; i++) {
            ts.addClause(adj[i][0], ans[i], adj[i][1], ans[i]);
            ts.addClause(adj[i][1], ans[i], adj[i][2], ans[i]);
            ts.addClause(adj[i][2], ans[i], adj[i][0], ans[i]);
        }
        if (!ts.satisfiable()) {
            break;
        }
    }
    for (int i = 0; i < N; i++) {
        std::cout << "BW"[ans[i]];
    }
    std::cout << "\n";
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int T;
    std::cin >> T;
    
    while (T--) {
        solve();
    }
    
    return 0;
}

提出情報

ジャッジ結果