TLE第二个点求助
查看原帖
TLE第二个点求助
442255
MichaelXucoutaendl楼主2023/7/10 20:00
#include <bits/stdc++.h>
#define N 1000010
#define M 1010
#define ll long long
#define READING ll
using namespace std;
inline READING read(){
	READING x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
void wrote(READING x){
	if (!x)return;
	wrote(x/10);
	putchar(x%10+'0');
}
void write(READING x,char f='\n'){
	if (x==0){putchar('0');putchar(f);return;}
	if (x<0){putchar('-');x=-x;}
	wrote(x);
	putchar(f);
}
struct node{
	int op,x,y;
}a[N];
int fa[N];
int find(int x){
	if (x==fa[x]) return x;
	return fa[x]=find(fa[x]);
}
void solve(){
	for (int i=0;i<N;i++) fa[i]=i;
	int n=read(),nowp=0;
	map<int,int> mp;
	for (int i=0;i<n;i++) a[i].x=read(),a[i].y=read(),a[i].op=read(),mp[a[i].x]=-1,mp[a[i].y]=-1;
	for (int i=0;i<n;i++){
		if (mp[a[i].x]==-1) a[i].x=mp[a[i].x]=nowp++;
		else a[i].x=mp[a[i].x];
		if (mp[a[i].y]==-1) a[i].y=mp[a[i].y]=nowp++;
		else a[i].y=mp[a[i].y];
	}
	for (int i=0;i<n;i++) if (a[i].op) if (find(a[i].x)!=find(a[i].y)) fa[find(a[i].x)]=find(a[i].y);
	for (int i=0;i<n;i++) if (!a[i].op){
		if (find(a[i].x)==find(a[i].y)){
			puts("NO");
			return;
		}
	}
	puts("YES");
}
int main()
{
	int t=read();
	while (t--) solve();
	return 0;
}
2023/7/10 20:00
加载中...