题解：[ARC188C] Honest or Liar or Confused

乍一看以为是 3-SAT 不可做，动动脑子发现是 2-SAT（

鉴于本题解书写时洛谷题面暂无中文翻译，为避免可能的歧义或困惑，先对本题解中的译法进行约定：

• 英文题面中“honest villager”或日文题面中“正直者”译为“诚实村民”。
• 英文题面中“liar”或日文题面中“嘘つき”译为“撒谎村民”。
• 英文题面中“confused”或日文题面中“混乱している”译为“糊涂的”。
• 英文题面中“not confused”或日文题面中“混乱していない”译为“清醒的”。
• 英文题面中“testimony”或日文题面中“証言”译为“证言”。

设 \(P_i\) 表示第 \(i\) 位村民是否是撒谎村民，\(Q_i\) 表示第 \(i\) 位村民是否是糊涂的。根据题意列出证言的真值表：

容易观察到证言 \((A,B,C)\) 实际上限制了 \(P_A\oplus Q_A\oplus P_B=C\)。

注意到，一位村民是否是撒谎村民和她是否清醒是无关的，并且上式中 \(P_A\) 和 \(Q_A\) 总是绑定在一起，因此不难想到设 \(R_i=P_i\oplus Q_i\)。证言 \((A,B,C)\) 的限制转化为 \(R_A\oplus P_B=C\)，是经典的 2-XOR-SAT 问题。使用扩展域并查集求解出 \(P_i\) 和 \(R_i\) 的一组解（或判定无解），再根据 \(Q_i=P_i\oplus R_i\) 求得并输出 \(Q_i\) 即可。

题目要求构造出一组解（而非判定是否有解），构造的过程比较容易想不清楚写错，赛时直接爽吃五发罚时。

核心代码：

//By: OIer rui_er
#define rep(x, y, z) for(int x = (y); x <= (z); ++x)
#define per(x, y, z) for(int x = (y); x >= (z); --x)

const int N = 8e5 + 5;

int n, m, ans[N];

struct Dsu {
    int fa[N];
    void init(int x) {rep(i, 1, x) fa[i] = i;}
    int find(int x) {return x == fa[x] ? x : fa[x] = find(fa[x]);}
    bool same(int x, int y) {return find(x) == find(y);}
    bool merge(int x, int y) {
        if(same(x, y)) return false;
        x = find(x); y = find(y);
        fa[x] = y;
        return true;
    }
}dsu;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> n >> m;
    dsu.init(4 * n);
    rep(i, 1, m) {
        int u, v, w;
        cin >> u >> v >> w;
        if(w == 0) {
            dsu.merge(u + 2 * n, v);
            dsu.merge(u + 2 * n + n, v + n);
        }
        else {
            dsu.merge(u + 2 * n, v + n);
            dsu.merge(u + 2 * n + n, v);
        }
    }
    rep(i, 1, n) {
        if(dsu.same(i, i + n)) {
            cout << "-1" << endl;
            return 0;
        }
        if(dsu.same(i + 2 * n, i + 2 * n + n)) {
            cout << "-1" << endl;
            return 0;
        }
    }
    // rep(i, 1, n) cout << dsu.find(i) << " " << dsu.find(i + n) << " " << dsu.find(i + 2 * n) << " " << dsu.find(i + 3 * n) << endl;
    rep(i, 1, n) {
        if(dsu.same(i, i + 2 * n)) cout << 0;
        else if(dsu.same(i, i + 2 * n + n)) cout << 1;
        else {
            dsu.merge(i + 2 * n, i);
            dsu.merge(i + 2 * n + n, i + n);
            cout << 0;
        }
    }
    cout << endl;
    return 0;
}