记录编号	197660	评测结果	AAAAAAAAAA
题目名称	[NOI 2015]程序自动分析	最终得分	100
用户昵称	神利·代目	是否通过	通过
代码语言	C++	运行时间	1.695 s
提交时间	2015-10-24 10:45:48	内存使用	7.83 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
int T,n,N,num,u,v,fa[200100];
struct shizi
{
	int x,y,e;
}o[100100];
struct tip
{
	int w,id;
}x[200100];
inline bool comp(tip a,tip b)
{
	return a.w<b.w;
}
inline bool cmp(shizi a,shizi b)
{
	return a.e>b.e;
}
inline int find(int x)
{
	if(fa[x]==x)
	    return x;
	return fa[x]=find(fa[x]);
}
int main()
{
	freopen("prog.in","r",stdin);
	freopen("prog.out","w",stdout);
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&n);
		memset(o,0,sizeof(o));
		for(int i=1;i<=n;++i)
		{
			scanf("%d%d%d",&x[i<<1].w,&x[i<<1|1].w,&o[i].e);
			x[i<<1].id=i;
			x[i<<1|1].id=i;
		}
		N=(n<<1|1);
		std::sort(x+2,x+N+1,comp);
		num=0;
		for(int i=2;i<=N;++i)
		{
			if(x[i].w!=x[i-1].w)
				++num;
			if(!o[x[i].id].x)
				o[x[i].id].x=num;
			else
			    o[x[i].id].y=num;
		}
		for(int i=1;i<=num;++i)
		    fa[i]=i;
		std::sort(o+1,o+n+1,cmp);
		int i=1;
		while(o[i].e)
		{
			u=find(o[i].x);
			v=find(o[i].y);
			if(u!=v)
				fa[v]=u;
			++i;
		}
		bool no=0;
		while(i<=n)
		{
			u=find(o[i].x);
			v=find(o[i].y);
			if(u==v)
				no=1;
			++i;
		}
		if(no)
		    puts("NO");
		else
		    puts("YES");
	}
}