比赛 |
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;
}