社区讨论

数据过水还是我的代码正确?

P3733[HAOI2017] 八纵八横参与者 3已保存回复 7

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
7 条
当前快照
1 份
快照标识符
@mhjhvl0k
此快照首次捕获于
2025/11/04 02:49
4 个月前
此快照最后确认于
2025/11/04 02:49
4 个月前
查看原帖
请注意看我代码中的 dfs\text{dfs} 函数,我没有判重边的情况,即 if (v != fa) ,但是我的代码却过了??
CPP
#include <bits/stdc++.h>
const int N = 505;
const int K = 1005;
typedef std::bitset<K> bit;

int n, m, q, tot, vis[N], pos[K], flag[K]; bit dis[N];
std::string s;
std::vector<std::pair<int, bit>> e[N];

bit base[K]; int t[K];
struct Que { int a, b, t; bit w; } que[K];

void insert(int tim, bit x) {
	for (int i = 1000; i >= 0; --i) {
		if (!x[i]) continue;
		if (!base[i].any()) { t[i] = tim; base[i] = x; return; }
		if (tim > t[i]) std::swap(tim, t[i]), std::swap(base[i], x);
		x ^= base[i];
	}
}

int stk[K], top;

void ask(int tim) {
	bit x; x.reset();
	for (int i = 1000; i >= 0; --i)	{
		if (tim > t[i]) continue;
		if (!x[i]) x ^= base[i]; 
	}

	for (int i = 0; x.any(); ++i)
		stk[top++] = x[i], x[i] = 0;
	for (int i = top - 1; ~i; --i)
		std::cout << stk[i]; std::cout << std::endl;
	top = 0;
}

void dfs(int u, int fa) {
	vis[u] = 1;
	for (auto [v, w] : e[u])
		if (v != fa) 
			if (vis[v]) insert(1e9, dis[u] ^ dis[v] ^ w);
			else dis[v] = dis[u] ^ w, dfs(v, u);
}

int main()
{
	std::ios::sync_with_stdio(0);
	std::cin.tie(0);
	std::cin >> n >> m >> q;
	for (int i = 1, u, v; i <= m; ++i) {
		std::cin >> u >> v >> s; bit w(s);
		e[u].emplace_back(v, w), e[v].emplace_back(u, w);
	}

	dfs(1, 0);

	for (int i = 1; i <= q; ++i) {
		std::cin >> s; int a, b;
		if (s[1] == 'd') {
			std::cin >> a >> b >> s; bit bi(s);
			pos[++tot] = i; flag[i] = 1;
			que[i] = {a, b, (int)1e9, bi};
		} else if (s[1] == 'h') {
			std::cin >> a >> s; bit bi(s);
			que[pos[a]].t = i - 1;
			que[i] = {que[pos[a]].a, que[pos[a]].b, (int)1e9, bi};
			pos[a] = i; flag[i] = 1;
		} else {
			std::cin >> a;
			que[pos[a]].t = i - 1;
		}
	}

	for (int i = 0; i <= q; ++i) {
		if (flag[i]) insert(que[i].t, dis[que[i].a] ^ dis[que[i].b] ^ que[i].w);
		ask(i);
	}

	return 0;
}

回复

7 条回复,欢迎继续交流。

正在加载回复...