赛时代码:
#include <bits/stdc++.h>
const int MAX = 5e5 + 5;
char _[5];
int x, y, c, T, n, m, ans;
int fa[MAX], siz[MAX], f[MAX];
std::bitset <MAX> g;
int find(int x)
{
if (fa[x] == x) { return x; } return fa[x] = find(fa[x]);
}
void merge(int x, int y)
{
x = find(x); y = find(y);
if (x == y) { return ; }
fa[x] = y; siz[y] += siz[x];
}
int inv(int x) { return (x > n ? x - n : x + n); }
int _inv(int x) { return (x == 3 ? 3 : (x == 2 ? 1 : 2)); }
void solve()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= 2 * n + 3; ++i) { fa[i] = f[i] = i; g[i] = false; siz[i] = 1; }
for (int i = 1; i <= m; ++i)
{
scanf("%s", _ + 1);
if (_[1] == '+')
{
scanf("%d%d", &x, &y);
if (g[y]) { f[x] = f[y]; f[inv(x)] = _inv(f[y]); g[x] = g[inv(x)] = true; }
else { f[x] = f[y]; f[inv(x)] = inv(f[y]); g[x] = g[inv(x)] = false; }
}
else if (_[1] == '-')
{
scanf("%d%d", &x, &y);
if (g[y]) { f[x] = _inv(f[y]); f[inv(x)] = f[y]; g[x] = g[inv(x)] = true; }
else { f[x] = inv(f[y]); f[inv(x)] = f[y]; g[x] = g[inv(x)] = false; }
}
else
{
scanf("%d", &x); g[x] = g[inv(x)] = true;
if (_[1] == 'U') { f[x] = f[inv(x)] = 3; }
else if (_[1] == 'T') { f[x] = 1; f[inv(x)] = 2; }
else { f[x] = 2; f[inv(x)] = 1; }
}
}
for (int i = 1; i <= 2 * n; ++i)
{
if (g[i]) { merge(i, 2 * n + f[i]); }
else { merge(i, f[i]); }
}
for (int i = 1; i <= n; ++i)
{
if (find(i) == find(n + i)) { merge(i, 2 * n + 3); }
}
printf("%d\n", (siz[find(2 * n + 3)] - 1) / 2);
}
int main()
{
freopen("tribool.in", "r", stdin);
freopen("tribool.out", "w", stdout);
scanf("%d%d", &c, &T); while (T--) { solve(); }
}
这份代码没有特判 - x x 的情况,这种情况应当 swap(f[x], f[inv(x)]),导致所以有此类型操作的点都会挂掉。考虑数据范围甚至可能 100→40。
同时 T1 没有判断 n=1 的情况。100→90。
改掉之后所有 OJ 的民间数据都能 A 掉。我是傻逼。我是傻逼。我是傻逼。可能因为这个要退役了。