蒟蒻求助,#2 MLE,内存限制500MB,其他点内存都不到3MB
查看原帖
蒟蒻求助,#2 MLE,内存限制500MB,其他点内存都不到3MB
181437
cyfff楼主2020/10/3 17:03
#include<bits/stdc++.h>
using namespace std;
struct node{int x,y,e;}a[100005];
bool cmp(node x,node y){return x.e>y.e;}
int t,n,i,j,k,f[100005],b[200005];bool fl;
inline int fd(int x){return x==f[x]?x:f[x]=fd(f[x]);}
inline int rd(){
	register int res=0,ff=1;register char ch=getchar();
	for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')ff=-1;
	for(;ch>='0'&&ch<='9';ch=getchar())res=res*10+ch-48;
	return res*ff;
}
int main(){
	for(t=rd();t--;){
		memset(a,0,sizeof(a));
		memset(b,0,sizeof(b));
		memset(f,0,sizeof(f));
		n=rd();j=0;
		for(i=1;i<=n;++i){
			a[i].x=rd();a[i].y=rd();a[i].e=rd();
			b[++j]=a[i].x;b[++j]=a[i].y;
		}
		sort(b+1,b+1+j);k=unique(b+1,b+1+j)-b;
		for(i=1;i<=n;++i){
			a[i].x=lower_bound(b+1,b+1+k,a[i].x)-b;
			a[i].y=lower_bound(b+1,b+1+k,a[i].y)-b;
		}
		for(i=1;i<=k;++i)f[i]=i;
		sort(a+1,a+1+n,cmp);fl=true;
		for(i=1;i<=n;++i){
			j=fd(a[i].x);k=fd(a[i].y);
			if(a[i].e&1)f[j]=k;
			else if(j==k){fl=false;break;}
		}
		puts(fl?"YES":"NO");
	}
	return 0;
}
2020/10/3 17:03
加载中...