社区讨论
为什么会错啊,求调玄关
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 条回复,欢迎继续交流。
正在加载回复...