#1191463 (C++17) No.3769 Even Contraction

• 問題: No.3769 Even Contraction
• ユーザー: marc2825
• 提出日時: 2026-10-04 20:44:23
• 言語: C++17 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: WA
• 実行時間: -
• コード長: 5,231 bytes
• コンパイル時間: 1,770 ms
• コンパイル使用メモリ: 233,936 KB
• 実行使用メモリ: 33,288 KB
• 最終ジャッジ日時: 2026-10-16 20:57:55
• 合計ジャッジ時間: 82,366 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge4_0

ファイルパターン	結果
sample	AC * 2 WA * 1
other	AC * 22 WA * 25

ソースコード

#include <bits/stdc++.h>
using namespace std;

using pii = pair<int,int>;

struct State {
    int N;
    vector<int> A;
    vector<char> alive;
    vector<unordered_set<int>> G;

    State(
        int N_,
        const vector<pii>& edges,
        const vector<int>& A_
    ) : N(N_), A(A_), alive(N_, true), G(N_) {
        for (auto [u,v] : edges) {
            G[u].insert(v);
            G[v].insert(u);
        }
    }

    bool connected(int u, int v) const {
        return alive[u] && alive[v] && G[u].count(v);
    }

    // u, v を縮約し、生き残った頂点番号を返す
    int contract_edge(int u, int v) {
        assert(connected(u,v));
        assert((A[u] & 1) == (A[v] & 1));

        int nv = (A[u] + A[v]) / 2;

        G[u].erase(v);
        G[v].erase(u);

        // small-to-large
        if (G[u].size() < G[v].size()) {
            swap(u,v);
        }

        vector<int> tmp(
            G[v].begin(),
            G[v].end()
        );

        for (int x : tmp) {
            G[x].erase(v);
            G[x].insert(u);
            G[u].insert(x);
        }

        G[v].clear();
        alive[v] = false;
        A[u] = nv;

        return u;
    }

    bool is02(int u, int v) const {
        return
            (A[u] == 0 && A[v] == 2) ||
            (A[u] == 2 && A[v] == 0);
    }

    bool same(int u, int v) const {
        return A[u] == A[v];
    }

    vector<pii> get_edges() const {
        vector<pii> es;

        for (int u=0; u<N; u++) {
            if (!alive[u]) continue;

            for (int v : G[u]) {
                if (u < v) {
                    es.push_back({u,v});
                }
            }
        }

        return es;
    }
};

mt19937_64 rng(
    chrono::steady_clock::now()
        .time_since_epoch().count()
);

// ------------------------------------------------------------
// 0-2 フェーズ
//
// 現在存在する 0-2 辺をランダムに並べ、
// 順番にまだ使えるものを縮約する。
//
// 1頂点が1度使われると値が1になるため、
// 実質的にはランダムな maximal matching を選ぶ感じ。
// ------------------------------------------------------------

int phase02(State& s) {
    vector<pii> cand;

    for (auto [u,v] : s.get_edges()) {
        if (s.is02(u,v)) {
            cand.push_back({u,v});
        }
    }

    shuffle(
        cand.begin(),
        cand.end(),
        rng
    );

    int cnt = 0;

    for (auto [u,v] : cand) {
        if (!s.connected(u,v)) continue;

        if (!s.is02(u,v)) continue;

        s.contract_edge(u,v);
        cnt++;
    }

    return cnt;
}

// ------------------------------------------------------------
// 同値フェーズ
//
// 0-0, 1-1, 2-2 をランダム順に縮約。
// 同値縮約によって新しい同値辺が生える可能性があるため、
// 何も縮約できなくなるまで繰り返す。
// ------------------------------------------------------------

int phase_same(State& s) {
    int total = 0;

    while (true) {
        vector<pii> cand;

        for (auto [u,v] : s.get_edges()) {
            if (s.same(u,v)) {
                cand.push_back({u,v});
            }
        }

        if (cand.empty()) break;

        shuffle(
            cand.begin(),
            cand.end(),
            rng
        );

        int cnt = 0;

        for (auto [u,v] : cand) {
            if (!s.connected(u,v)) continue;

            if (!s.same(u,v)) continue;

            s.contract_edge(u,v);

            cnt++;
            total++;
        }

        if (cnt == 0) break;
    }

    return total;
}

// ------------------------------------------------------------
// 1試行
//
// 0-2
// ↓
// 同値
// ↓
// 0-2
// ↓
// 同値
// ...
//
// と収束まで繰り返す。
// ------------------------------------------------------------

int trial(
    int N,
    const vector<pii>& edges,
    const vector<int>& A
) {
    State s(N,edges,A);

    int ans = 0;

    while (true) {
        int add = 0;

        add += phase02(s);
        add += phase_same(s);

        ans += add;

        if (add == 0) {
            break;
        }
    }

    return ans;
}

void solve() {
    int N;
    cin >> N;

    vector<pii> edges;

    for (int i = 0; i < N - 1; i++) {
        int u, v;
        cin >> u >> v;
        --u;
        --v;

        edges.push_back({u, v});
    }

    vector<int> A(N);

    for (int& x : A) {
        cin >> x;
    }

    int ans = 0;

    auto start = chrono::steady_clock::now();

    // 2秒制限なので少し余裕を持たせる
    constexpr double TIME_LIMIT = 1.85;

    int trials = 0;

    while (true) {
        auto now = chrono::steady_clock::now();

        double elapsed =
            chrono::duration<double>(now - start).count();

        if (elapsed >= TIME_LIMIT) {
            break;
        }

        ans = max(
            ans,
            trial(N, edges, A)
        );

        trials++;

        // 理論上限まで行ったら即終了
        if (ans == N - 1) {
            break;
        }
    }

    // cerr << "trials = " << trials << '\n';

    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    solve();
}