90分WA
查看原帖
90分WA
676403
Skyboys楼主2024/2/28 22:12

#3下载数据后测试输出答案一致(雾

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr)
#define int long long
#define PII pair<int,int>
#define fp(a,b,c,d) for(register int a=b;a<=c;a+=d)
#define fm(a,b,c,d) for(register int a=b;a>=c;a-=d)
#define ms(a,b) memset(a,b,sizeof a);
#define mc(a,b) memcpy(a,b,sizeof a);
#define lowbit(a) (a&(-a))
#define fxs(a) fixed<<setprecision(a)
#define fi first
#define se second
using namespace std;
const int N = 1000010,INF = 0x3f3f3f3f,MOD = 1e9 + 7;
inline int read(){int f=1,k=0;char c=getchar(); while(c<'0'||c>'9')c=getchar();while(c>='0' && c<='9'){k=k*10+c-'0';c=getchar();}return f*k;}
struct S{
	int x,y,eq;
	void read(){cin>>x>>y>>eq;}
}a[N];
bool cmp(S q,S w){return q.eq>w.eq;}
int n,s[N],old[N],tot=0;
void init(int m){fp(i,1,m,1)s[i]=i;}
int find(int x){return (s[x]==x ? s[x] : s[x]=find(s[x]));}
void merge(int x,int y){s[find(x)]=find(y);}
signed main()
{
	IOS;
	int t;cin>>t;
	while(t--){
		cin>>n;
		tot=0;
		fp(i,1,n,1){
			a[i].read();
			old[++tot]=a[i].x;
			old[++tot]=a[i].y;
		}
		sort(old+1,old+tot+1);
		int newn=unique(old+1,old+tot+1)-old;
		init(newn);
		fp(i,1,n,1){
			a[i].x=lower_bound(old+1,old+newn+1,a[i].x)-old;
			a[i].y=lower_bound(old+1,old+newn+1,a[i].y)-old;
		}
		sort(a+1,a+n+1,cmp);
		bool f=true;
		fp(i,1,n,1){
			int fx=find(a[i].x);
			int fy=find(a[i].y);
			if(a[i].eq==1)merge(a[i].x,a[i].y);
			else if(fx==fy){
				cout<<"NO"<<endl;
				f=false;
				break;
			}
		}
		if(f)cout<<"YES"<<endl;
	}
	return 0;
}

2024/2/28 22:12
加载中...