提出 #63534304

---

ソースコード 拡げる

#include <iostream>
#include <vector>
#include <cassert>
using namespace std;
const int B = 30;
struct Instruction {
    int v; int should_flip;
    Instruction(int v, int should_flip): v(v), should_flip(should_flip) {}
};
void solve() {
    int n, m; cin >> n >> m;
    vector<int> x(m), y(m), z(m);
    for (int j = 0; j < m; j++) {
        cin >> x[j] >> y[j] >> z[j];
        x[j]--, y[j]--;
    }

    vector<int> solution(n);
    for (int b = 0; b < B; b++) {
        vector<vector<Instruction>> adj(n);
        for (int j = 0; j < m; j++) {
            int u = x[j];
            int v = y[j];
            bool should_flip = z[j] & (1 << b);
            // cout << u << " " << v << " " << should_flip << endl;
            adj[u].emplace_back(v, should_flip);
            adj[v].emplace_back(u, should_flip);
        }
        // cout << endl;

        vector<int> final_color(n, -1);
        vector<bool> done(n, false);
        auto do_color = [&adj, &done, &final_color](int u, int color, int& zero_count, vector<int>& encountered, auto do_color) -> bool {
            if (done[u]) {
                return final_color[u] == color;
            }
            done[u] = true;

            final_color[u] = color;
            if (color == 0) {
                zero_count++;
            }
            encountered.push_back(u);

            for (auto[v, should_flip]: adj[u]) {
                if (!do_color(v, color ^ should_flip, zero_count, encountered, do_color)) {
                    return false;
                }
            }
            return true;
        };

        for (int u = 0; u < n; u++) {
            if (!done[u]) {
                int zero_count = 0;
                vector<int> encountered;
                bool attempt = do_color(u, 0, zero_count, encountered, do_color);
                if (!attempt) {
                    cout << -1 << endl;
                    return;
                }
                int one_count = encountered.size() - zero_count;
                if (!(zero_count >= one_count)) {
                    for (int to_flip : encountered) {
                        final_color[to_flip] ^= 1;
                    }
                }
            }
        }
        for (int i = 0; i < n; i++) {
            assert(final_color[i] != -1);
            if (final_color[i] == 1) {
                solution[i] += 1 << b;
            }
        }
    }
    for (int i = 0; i < n; i++) {
        cout << solution[i] << (i == n-1 ? '\n' : ' ');
    }
}
int main() {
    solve();
    return 0;
}

提出情報

ジャッジ結果