社区讨论

萌新刚学带权并查集 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 条回复,欢迎继续交流。

正在加载回复...