社区讨论

为什么会错啊,求调玄关

P13308故障参与者 1已保存回复 0

讨论操作

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

当前回复
0 条
当前快照
1 份
快照标识符
@mhjhmgdh
此快照首次捕获于
2025/11/04 02:42
4 个月前
此快照最后确认于
2025/11/04 02:42
4 个月前
查看原帖
思路是先把要删的边全删掉,然后反向操作,删边改为加边,每一个删掉与父结点连接边的结点都建立并查集并用离散化映射,查找时向上查找最近的删边的点并输出连通块大小,能想到的样例全对,为什么0分啊?
CPP
#include<bits/stdc++.h>
using namespace std;
#define ll  long long
#define int long long
#define db long double

inline ll read(){
	ll res = 0, f = 1;
	char c = getchar();
	while(c > '9' || c < '0'){
		if(c == '-')f = -1;
		c = getchar();
	}
	while(c <= '9' && c >= '0'){
		res = res * 10 + c - '0';
		c = getchar();
	}
	return f * res;
}
const int N = 500010;

unordered_map<ll, bool>st;
unordered_map<ll, ll>ma;

struct i{
	bool op;
	ll p;
}cz[N];
ll siz[N], p[N];
ll ceng(ll p){
	ll res = 0;
	while((1ll << res) <= p){
		res ++;
	}
	return res;
}
ll find(ll a){
	if(p[a] == a)return a;
	return p[a] = find(p[a]);
}
signed main(){
	freopen("test.in", "r", stdin);
	freopen("test.out", "w", stdout);
	vector<ll>del;
	ll n = read(), m = read(), cz_idx = 0, p_idx = 1;
	ma[1] = 1;
	st[1] = 1;
	p[1] = 1;
	siz[1] = (1ll << (n - ceng(1) + 1)) - 1;
	for(int i = 1; i <= m; i ++){
		ll o = read(), u = read();
		if(o == 1){
			if(st[u] == 1)continue;
			del. push_back(u);
			st[u] = 1;
			cz[++ cz_idx] = {1, u};
			ma[u] = ++ p_idx;
			p[p_idx] = p_idx;
			siz[p_idx] = (1ll << (n - ceng(u) + 1)) - 1;
		}
		else{
			cz[++ cz_idx] = {0, u};
		}
	}
	for(auto it = del. begin(); it != del. end(); it ++){
		ll now = *it;
		ll sizee = siz[ma[now]];
		now >>= 1;
		while(!st[now] && now != 1){
			now >>= 1;
		}
		siz[ma[now]] -= sizee;
	}
	ll ans = 0;
	for(int i = cz_idx; i >= 1; i --){
		ll now = cz[i]. p;
		if(cz[i]. op){
			ll sizee = siz[find(ma[now])];
			ll mid = now;
			st[now] = 0;
			now >>= 1;
			while(!st[now] && now != 1)now >>= 1;
			siz[find(ma[now])] += sizee;
			p[find(ma[mid])] = find(ma[now]);
		}
		else{
			while(!st[now] && now != 1)now >>= 1;
			ans ^= siz[find(ma[now])];
			// cout << siz[find(ma[now])] << endl;
		}
	}
	cout << ans;
	return 0;
}
//yandex

回复

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

正在加载回复...