并查集求助 不吸氧100pts 吸氧0
查看原帖
并查集求助 不吸氧100pts 吸氧0
756805
xuweiyi楼主2023/6/29 11:41

蒟蒻求调,在线等qAq

情况:RE on #2

#2 Devc++的freopen的输出文件结果和洛谷给的完全一样。

吸氧0pts,不吸氧100pts

100pts测试点

0pts测试点

出错代码

#include<bits/stdc++.h>
using namespace std;
#define maxn 100007
inline int read();
struct p{
	int i1,i2,val;
};p a[maxn];
int n,t,b[maxn*2],top=0,bcj[maxn*2];
unordered_map<int,int>mp;
inline void init(){
	mp.clear();top=0;
	for(int i=1;i<=maxn*2;++i){
		bcj[i]=i;
	}return;
}
inline int find(int x){
	if(bcj[x]==x) return x;
	return bcj[x]=find(bcj[x]); 
}
inline void merge(int x,int y){
	x=find(x),y=find(y);
	bcj[x]=y;
}
inline bool qwq(){
	for(int i=1;i<=n;++i){
		if(a[i].val==0&&find(a[i].i1)==find(a[i].i2)){
			return false;
		}
	}return true;
}
int main(){
	//freopen("P1955_2.in","r",stdin);
	//freopen("qwq.out","w",stdout);
	t=read();
	while(t--){
		init();
		n=read();
		for(int i=1;i<=n;++i){
			a[i]={read(),read(),read()};
			b[++top]=a[i].i1,b[++top]=a[i].i2;
		}
		sort(b+1,b+top+1);
		top=unique(b+1,b+top+1)-b;
		for(int i=1;i<=top;++i){
			mp[b[i]]=i;
		}
		for(int i=1;i<=n;++i){
			a[i].i1=mp[a[i].i1];
			a[i].i2=mp[a[i].i2];
			if(a[i].val==1){
				merge(a[i].i1,a[i].i2);
			}
		}
		(qwq()==true)?puts("YES"):puts("NO");
	}
	return 0;
}
inline int read(){
	int x=0,f=1;char ch=getchar();
	while(ch>'9'||ch<'0'){
		if(ch=='-'){
			f=-1;
		}ch=getchar();
	}
	while(ch<='9'&&ch>='0'){
		x*=10;x+=int(ch-'0');
		ch=getchar();
	}
	return x*f;
}
2023/6/29 11:41
加载中...