4005번: 테이블 색칠하기

https://www.acmicpc.net/problem/4005

#include<cstdio>
#include<vector>
#define mod int(1e9)
using namespace std;
const int MX = 1e5;
int n, m, k, r = 1, vis[MX + 1], c[MX + 1], ck[MX + 1], tcnt, ccnt;
vector<pair<int, int> > row[MX + 1];
vector<int> col[MX + 1];
void f(int h) {
    if (vis[h]) return;
    vis[h] = 1;
    int cnt = 0, tot = 0;
    for (auto it : row[h]) if (ck[it.first]) {
        tot++;
        int ans = it.second ^ (h&it.first & 1);
        if (c[it.first] ^ ans) cnt++;
    }
    if (0 < cnt && cnt < tot) r = 0;
    for (auto it : row[h]) if (!ck[it.first]) {
        tcnt++;
        ck[it.first] = 1;
        c[it.first] = it.second^cnt > 0 ^ (h&it.first & 1);
    }
    for (auto it : row[h]) if (ck[it.first] == 1) {
        ck[it.first]++;
        for (int t : col[it.first]) f(t);
    }
}
int main() {
    scanf("%d%d%d", &n, &m, &k);
    while (k--) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        row[a].push_back({ b,c });
        col[b].push_back(a);
    }
    ccnt = m - 1;
    for (int i = 1; i <= n; i++) {
        tcnt = 0;
        f(i);
        if (tcnt) ccnt -= tcnt - 1;
    }
    while (ccnt--) r = (r * 2) % mod;
    for (int i = 1; i <= n; i++) if (row[i].empty()) r = (r * 2) % mod;
    printf("%d", r);
    return 0;
}