记录编号	303712	评测结果	AAAAAAAAAA
题目名称	[NOI 2015]程序自动分析	最终得分	100
用户昵称	liu_runda	是否通过	通过
代码语言	C++	运行时间	1.883 s
提交时间	2016-09-06 15:56:50	内存使用	31.16 MiB

#include<cstdio>
#include<algorithm>
using namespace std; 
const int maxn=1000005;
int num[maxn*2];
int dic[maxn*2];
int typ[maxn];
int seq[maxn*2];
bool cmp(const int &a,const int &b){
    return num[a]<num[b];
}
int ufs[maxn*2];
int find(int x){
	int rt=x;
	while(ufs[rt]!=rt)rt=ufs[rt];
	int rt2=x;
	while(ufs[rt2]!=rt2){
		int tmp=rt2;
		rt2=ufs[rt2];
		ufs[tmp]=rt;
	}
	return rt;
}
void link(int a,int b){
	ufs[find(a)]=find(b);
}
int main(){
	freopen("prog.in","r",stdin);
	freopen("prog.out","w",stdout);
	int t;scanf("%d",&t);
	while(t--){
		int n;scanf("%d",&n);
		for(int i=0;i<n;++i){
            scanf("%d %d %d",num+i*2,num+i*2+1,typ+i);
		}
		int n2=n*2;
		for(int i=0;i<n2;++i)seq[i]=i;
		sort(seq,seq+n2,cmp);
		int tot=0,old=-1;
		for(int i=0;i<n2;++i){
			if(num[seq[i]]!=old)++tot,old=num[seq[i]];
			dic[seq[i]]=tot;
		}
		for(int i=1;i<=n2;++i)ufs[i]=i;
		for(int i=0;i<n;++i){
			if(typ[i]==1)link(dic[i*2],dic[i*2+1]);
		}
		bool flag=true;
		for(int i=0;i<n;++i){
			if(typ[i]==0&&find(dic[i*2])==find(dic[i*2+1])){
				flag=false;break;
			}
		}
		if(flag)printf("YES\n");
		else printf("NO\n");
	}
	fclose(stdin);fclose(stdout);
	return 0;
}