社区讨论
萌新刚学带权并查集 1ms,离奇全 WA 求助
P1196[NOI2002] 银河英雄传说参与者 3已保存回复 9
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 9 条
- 当前快照
- 1 份
- 快照标识符
- @lo8dcx2p
- 此快照首次捕获于
- 2023/10/27 16:46 2 年前
- 此快照最后确认于
- 2023/10/27 16:46 2 年前
rt,
CPP#include <bits/stdc++.h>
using namespace std;
inline int read(){
int x=0;bool f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=0;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return f?x:-x;
}
int t,x,y,f[30005],fx,fy,num[30005],fr[30005];
char op;
int find(int x){
if(x==f[x]) return x;
int fax=find(f[x]);
fr[x]+=fr[f[x]];
return f[x]=fax;
}
int main(){
t=read();
for(int i=1;i<=30000;i++)
f[i]=i,num[i]=1;
while(t--){
op=getchar(),x=read(),y=read();
fx=find(x),fy=find(y);
if(op^'M') printf("%d\n",(fx^fy)?-1:abs(fr[x]-fr[y])-1);
else fr[fx]+=num[fy],f[fx]=fy,num[fy]+=num[fx],num[fx]=0;
}
return 0;
}
但是在我校 oj 上以最大点 822ms 的好成绩 T 了三个点?
回复
共 9 条回复,欢迎继续交流。
正在加载回复...