牛客练习赛39D

牛客练习赛39D

n,m<=5e4;

首先操作2用并查集就行了。题解说的好啊!

考虑操作一,连的两个点如果同色,直接合并,然后这个颜色的联通块-1,然后合并bitset,就是或一下。bitset维护的是相连的异色结点。

如果两个点异色,那么我们就不管他们,直接在两个bitset里分别把对方设为1。

对于操作三 直接 (b[x]&b[y]).count(); 就行了。

 #include <bits/stdc++.h>
using namespace std;
const int N = 5e4+;
int fa[N];
bitset<> b[N];
int find(int a){
return a==fa[a]?a:fa[a]=find(fa[a]);
}
int n,m,op,x,y,c[N]; int main(){
ios::sync_with_stdio(false);
cin>>n>>m;
int hei=,bai;
for(int i=;i<=n;i++){
fa[i]=i;cin>>c[i];
hei+=c[i];
}
bai=n-hei;
while (m--){
cin>>op;
if(op==){
cin>>x>>y;
int xx=x,yy=y;
x=find(x);y=find(y);
if(x==y)continue;
if(c[xx]==){
if(c[yy]==)fa[y]=x,hei--,b[x]|=b[y];
else b[x][yy]=,b[y][xx]=;
} else{
if(c[yy]==)fa[y]=x,bai--,b[x]|=b[y];
else b[x][yy]=,b[y][xx]=;
}
} else if(op==){
cin>>x;
if(!x)cout<<bai<<endl;
else cout<<hei<<endl;
} else{
cin>>x>>y;
x=find(x);y=find(y);
if(x==y)cout<<-<<endl;
else{
cout<<(b[x]&b[y]).count()<<endl;
}
}
}
}
上一篇:Python问题:SyntaxError: Non-ASCII character '\xe2' in file


下一篇:Direct3D11学习:(二)基本绘图概念和基本类型