傻逼操作把自己挂大分
  • 板块学术版
  • 楼主AtomAlpaca
  • 当前回复5
  • 已保存回复6
  • 发布时间2023/11/18 19:59
  • 上次更新2023/11/18 21:12:44
查看原帖
傻逼操作把自己挂大分
374500
AtomAlpaca楼主2023/11/18 19:59

赛时代码:

#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→40100 \to 40。

同时 T1 没有判断 n=1n=1 的情况。100→90100\to 90。

改掉之后所有 OJ 的民间数据都能 A 掉。我是傻逼。我是傻逼。我是傻逼。可能因为这个要退役了。

2023/11/18 19:59
加载中...