总超时三个点
查看原帖
总超时三个点
648660
Name1楼主2022/4/15 13:49
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio> 
using namespace std;
const int p=100005;
struct node{
	int x,y,fl;
	bool operator <(const node a)const{return a.fl<fl;}
}a[p];
int n,f[p],book[p<<1],tot,tott,t;
inline int read()
{
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();}
	while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
	return x*f;
}
inline int find(int x) {return x==f[x]?x:x=find(f[x]);}

int main()
{
	t=read();
	while(t--)
	{
	memset(a,0,sizeof(a));
	memset(book,0,sizeof(book));
	memset(f,0,sizeof(f));tot=0;
	n=read();
	for(int i=1;i<=n;i++) 
	{
		a[i].x=read(),a[i].y=read(),a[i].fl=read();
		book[++tot]=a[i].x,book[++tot]=a[i].y;
	}
	sort(book+1,book+1+tot);
	tott=unique(book+1,book+1+tot)-book;
	for(int i=1;i<=n;i++)
	{
		a[i].x=lower_bound(book+1,book+1+tott,a[i].x)-book;
		a[i].y=lower_bound(book+1,book+1+tott,a[i].y)-book;
	}
	sort(a+1,a+1+n);
	for(int i=1;i<=tott;i++) f[i]=i;
	bool flag=true;
	for(int i=1;i<=n;i++)
	{
		int fl=a[i].fl,ax=find(a[i].x),ay=find(a[i].y);
		if(fl==1&&ax!=ay)
			f[ax]=ay;
		else if(fl==0&&ax==ay)
		{
			flag=false;
			break;
		}
	}
	if(flag==false)puts("NO");
	else puts("YES");
	}
	return 0;
}

求大佬帮忙看看

2022/4/15 13:49
加载中...