比赛 NOI2015Day1 评测结果 AAAAAAAAAA
题目名称 程序自动分析 最终得分 100
用户昵称 NVIDIA 运行时间 1.618 s
代码语言 C++ 内存使用 339.79 MiB
提交时间 2015-08-01 12:52:06
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<map>
#include<queue>
#include<vector>
#include<stdio.h>
using namespace std;
const int M = 9888888;
int N, T;
int fa[M*2];
int data[M][2];
int b[M*2]; 
int arr[M*2],cnt,len;
void get(int &r) 
{
    char c; r=0;
    do c=getchar(); 
	while (c<'0'||c>'9');
    do{r=r*10+c-'0';
	c=getchar();}
	while (c>='0'&&c<='9');
}
int fd(int x)
{  
	int l = 1, r = len, mid = (l + r) >> 1;
	while (l < r) 
	{
		if (arr[mid] == x) return mid;
		if (arr[mid] < x) l = mid + 1;
		else r = mid - 1;
		mid = (l+r) >> 1;
	}
	return mid;
}

struct Stack 
{ 
	int sta[M*2],tp;
	bool empty() {return tp==0;}
	int top() {return sta[tp];}
	void push(int x) {sta[++tp]=x;}
	void pop(){--tp;}
	void clear(){tp=0;}
} z;

void init() 
{
	for (int i = 1; i<=len; ++i)
		fa[i] = i;
}
int root(int x)
{ 
	while (fa[x] != x && x != -1) z.push(x), x = fa[x];
	while (!z.empty()) fa[z.top()] = x, z.pop();
	return x;
}

bool solve() 
{
	init();
	int i, t1, t2;
	for (i = 1; i<=N; ++i)
		if (b[i] == 1) 
		{
			t1 = fd(data[i][0]);
			t2 = fd(data[i][1]);
			if (root(t1) != root(t2))
				fa[root(t1)] = root(t2);
		}
	for (i = 1; i<=N; ++i)
		if (b[i] == 0) 
		{
			t1 = fd(data[i][0]);
			t2 = fd(data[i][1]);
			if (root(t1) == root(t2))
				return 0;
		}
	return 1;
}

int main()
{
freopen("prog.in", "r", stdin);
freopen("prog.out", "w", stdout);
int i;
get(T);
while (T--)
{
get(N);
cnt = 0;
for (i = 1; i<=N; ++i) 
{
			get(data[i][0]); get(data[i][1]);
			get(b[i]);
			arr[++cnt] = data[i][0];
			arr[++cnt] = data[i][1];
		}
sort(arr+1, arr+cnt+1);
len = unique(arr+1, arr+cnt+1) - (arr+1); 
if (solve()) cout<<"YES";
		 else cout<<"NO";
	}
	return 0;
}