比赛 NOI2015Day1 评测结果 AAAAAAAAAA
题目名称 程序自动分析 最终得分 100
用户昵称 stdafx.h 运行时间 1.144 s
代码语言 C++ 内存使用 34.62 MiB
提交时间 2015-08-01 08:02:39
显示代码纯文本
#define MAXN 1000010UL

#include <cstdio>
#include <algorithm>

struct Query{
	int a,b,r;
};

struct ls{
	int data,index;
};

Query p[MAXN];
ls s[MAXN<<1];

int n,father[MAXN<<1];

inline int in(){
	int x=0,ch=getchar();
	while(ch<'0'||ch>'9'){
		ch=getchar();
	}
	for(;ch>='0'&&ch<='9';ch=getchar()){
		x=x*10+ch-48;
	}
	return x;
}

inline bool comp(ls a,ls b){
	return a.data<b.data;
}

inline bool comp2(Query a,Query b){
	return a.r>b.r;
}

int getf(int x){
	if(father[x]!=x) father[x]=getf(father[x]);
	return father[x];
}

void Work(){
	n=in();
	int n2=n<<1;
	for(int i=1;i<=n2;i++){
		father[i]=i;
	}
	for(int i=1;i<=n;i++){
		s[(i-1)<<1|1].data=in();s[i<<1].data=in();p[i].r=in();
		s[i].index=i;
	}
	for(int i=n+1;i<=n2;i++){
		s[i].index=i;
	}
	std::sort(s+1,s+n2+1,comp);
	int num=0;
	for(int i=1;i<=n2;i++){
		if(s[i].data!=s[i-1].data){
			++num;
		}
		if(s[i].index&1){
			p[(s[i].index>>1)+1].a=num;
		}
		else{
			p[s[i].index>>1].b=num;
		}
	}
	std::sort(p+1,p+n+1,comp2);
	for(int i=1;i<=n;i++){
		int k1=getf(p[i].a),k2=getf(p[i].b);
		if(p[i].r){
			father[k1]=k2;
		}
		else{
			if(k1==k2){
				puts("NO");
				return;
			}
		}
	}
	puts("YES");
	return;
}

int main(){
	freopen("prog.in","r",stdin);
	freopen("prog.out","w",stdout);
	int t=in();
	for(int i=1;i<=t;i++){
		Work();
	}
	return 0;
}