P3631 [APIO2011] 方格染色

#include <algorithm>
#include <iostream>
#include <utility>
#include <vector>
using namespace std;
constexpr int N  = 1e5 + 5;
constexpr int M  = 1e9;
using vi         = vector<int>;
using constraint = pair<int, int>;

struct ColouredCell {
    int x, y, c;
} cc[N];
int n, m, k;
int mapping(int x, int y) {
    if (y == 0) return x;
    else return y + n;
}
vector<constraint> G[N << 1];
int vis[N << 1], val[N << 1];

int main() {
    cin >> n >> m >> k;
    for (int i = 1; i <= k; i++) {
        cin >> cc[i].x >> cc[i].y >> cc[i].c;
        if (cc[i].x % 2 == 1 && cc[i].y % 2 == 1) {
            int a = mapping(cc[i].x, 0);
            int b = mapping(0, cc[i].y);
            G[a].push_back({b, cc[i].c});
            G[b].push_back({a, cc[i].c});
        } else {
            int a = mapping(cc[i].x, 0);
            int b = mapping(0, cc[i].y);
            G[a].push_back({b, cc[i].c ^ 1});
            G[b].push_back({a, cc[i].c ^ 1});
        }
    }

    auto dfs = [&](auto &&F, int u) -> bool {
        vis[u] = 1;
        // cerr << u << " ";
        for (auto [v, cons] : G[u]) {
            if (vis[v]) {
                if ((val[v] ^ val[u]) != cons) return false;
                continue;
            }
            val[v] = val[u] ^ cons;
            if (!F(F, v)) return false;
        }
        return true;
    };

    int cnt = -2;
    for (int i = 0; i <= n + m; i++) {
        if (vis[i]) continue;
        cnt++;
        if (!dfs(dfs, i)) {
            cout << 0 << '\n';
            return 0;
        }
        // cerr << "\n";
    }

    int b = 2, p = cnt;
    int res = 1;
    while (p) {
        if (p & 1) res = 1ll * res * b % M;
        b = 1ll * b * b % M;
        p >>= 1;
    }
    cout << res << '\n';
}