题解

题目要判断是否能够通过设置每个开关的状态，使所有管道至少有一个阀门关闭。把“开关 $i$ 取值为 0/1”视作布尔变量 $x_i$，单个阀门处于关闭状态意味着 “$x_i = s$”（其中 $s$ 由输入给出）。一个管道有两个阀门，只要其中至少一个关闭即可，于是得到一个析取子句 $(x_a = s_a) \lor (x_b = s_b)$。这样所有约束都变成了 2-SAT。

实现时将变量 $x_i$ 的正反两个取值映射为下标 $2i$ 与 $2i+1$，add(u, v) 按 2-SAT 标准建边（$\lnot u \rightarrow v$、$\lnot v \rightarrow u$）。对整个含义图执行 Tarjan 强连通分量分解：如果某个变量的两个取值落入同一个 SCC，则无解；否则按照 SCC 拓扑序比较 col[2*i] 与 col[2*i+1] 的先后，较大的那一个代表赋值为真。

这种建模可以在线性时间内（对于每条输入管道生成常数条边）完成，并用 Tarjan 在 $O(n+m)$ 复杂度内求解。最后输出每个开关应该取的状态即可；若检测到矛盾则输出 IMPOSSIBLE。

#include <bits/stdc++.h>
#define RNG(V_, A_, B_) for (int V_ = (A_), V_##_END = (B_); V_ <= V_##_END; V_++)
#define IRNG(V_, A_, B_) for (int V_ = (A_), V_##_END = (B_); V_ >= V_##_END; V_--)
using namespace std;
const int MAXN = 1e6+10;
int n, m;
struct TwoSAT {
    vector<int> G[MAXN];
    void add(int i, int j) { G[i^1].push_back(j), G[j^1].push_back(i); }
    int dfn[MAXN], low[MAXN], dfncnt, instk[MAXN], stk[MAXN], stktop, col[MAXN], colcnt;
    void tarjan(int u) {
        dfn[u] = low[u] = ++dfncnt, instk[u] = true, stk[++stktop] = u;
        for (auto v : G[u]) {
            if (!dfn[v]) tarjan(v), low[u] = min(low[u], low[v]);
            else if (instk[v]) low[u] = min(low[u], dfn[v]);
        }
        if (dfn[u] == low[u]) {
            int v, c = ++colcnt;
            do {
                instk[v = stk[stktop--]] = false;
                col[v] = c;
            } while (v != u);
        }
    }
    bool solve() {
        RNG(u, 2, 2*n+1) {
            if (!dfn[u]) tarjan(u);
        }
        RNG(u, 1, n) {
            if (col[2*u] == col[2*u+1]) return false;
        }
        return true;
    }
} twosat;
int main() {
    scanf("%d%d", &m, &n);
    RNG(_, 1, m) {
        int i, a, j, b;  scanf("%d%d%d%d", &i, &a, &j, &b);
        twosat.add(i*2+a, j*2+b);
    }
    if (twosat.solve()) {
        RNG(i, 1, n) printf("%d\n", twosat.col[i*2] > twosat.col[i*2+1]);
    } else printf("IMPOSSIBLE\n");
}