Codeforces 1971H ±1

考虑到因为只有 \(3\) 行，所以第 \(2\) 行为 \(1\) 的条件就是 \(1\) 的个数 \(\ge 2\)。

对于这种只能去正负且有无解的问题，可以想到用个 \(\text{2-SAT}\)。
于是接下来考虑用 \(\operatorname{AND}, \operatorname{OR}, \operatorname{XOR}\) 来表示至少有 \(2\) 个 \(1\)。
考虑到如果存在 \(2\) 个 \(0\)，那么这两个数 \(\operatorname{OR}\) 肯定为 \(0\)。
否则如果存在 \(2\) 个 \(1\)，任意选出 \(2\) 个肯定都存在 \(1\)，\(\operatorname{OR}\) 为 \(1\)。
于是可以得到限制 \(p_1\operatorname{OR} p_2 = p_1\operatorname{OR} p_3 = p_2\operatorname{OR} p_3 = 1\)。
于是建图缩点就可以了。

时间复杂度 \(\mathcal{O}(n)\)。

#include<bits/stdc++.h>
const int maxn = 1e3 + 10;
std::vector<int> to[maxn];
int a[3][maxn];
int dfn[maxn], low[maxn], fa[maxn], dt, ft, stk[maxn], top, ins[maxn];
void dfs(int u) {
   dfn[u] = low[u] = ++dt, stk[++top] = u, ins[u] = 1;
   for (int v : to[u]) {
      if (! dfn[v])
         dfs(v), low[u] = std::min(low[v], low[u]);
      else if (ins[v])
         low[u] = std::min(low[u], dfn[v]);
   }
   if (low[u] < dfn[u])
      return ;
   ft++;
   int t;
   do {
      t = stk[top--];
      ins[t] = 0, fa[t] = ft;
   } while (t != u);
}
inline void Main() {
   int n;
   scanf("%d", &n);
   for (int i : {0, 1, 2})
      for (int j = 1; j <= n; j++)
         scanf("%d", &a[i][j]);
   for (int i = 1; i <= n * 2; i++)
      to[i].clear();
   auto id = [&](int x) {return x < 0 ? -x : (x + n);};
   auto oth = [&](int x) {return x > n ? (x - n) : (x + n);};
   auto add = [&](int x, int y) {to[x].push_back(y);};
   for (int i = 1; i <= n; i++) {
      for (int j : {0, 1, 2}) for (int k : {0, 1, 2})
         if (j != k) 
            add(oth(id(a[j][i])), id(a[k][i]));
   }
   memset(dfn, 0, sizeof(int) * (n * 2 + 1));
   memset(low, 0, sizeof(int) * (n * 2 + 1));
   dt = ft = 0;
   for (int i = 1; i <= n * 2; i++)
      ! dfn[i] && (dfs(i), 1);
   for (int i = 1; i <= n; i++)
      if (fa[i] == fa[n + i])
         return puts("NO"), void();
   puts("YES");
}
int main() {
   int T;
   scanf("%d", &T);
   while (T--) Main();
   return 0;
}