P1955 [NOI2015]程序自动分析[离散化+并查集]

一看就是离散化,先去满足相等的条件,相等即为两点联通,或者说在同一个集合内。再看不相等,只有两元素在同一集合才不满足。裸的disjoint-set直接上,常数巨大什么的不管啦。

 #include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#define dbg(x) cerr<<#x<<" = "<<x<<endl
#define ddbg(x,y) cerr<<#x<<" = "<<x<<" "<<#y<<" = "<<y<<endl
using namespace std;
typedef long long ll;
template<typename T>inline char MIN(T&A,T B){return A>B?A=B,:;}
template<typename T>inline char MAX(T&A,T B){return A<B?A=B,:;}
template<typename T>inline T _min(T A,T B){return A<B?A:B;}
template<typename T>inline T _max(T A,T B){return A>B?A:B;}
template<typename T>inline T read(T&x){
x=;int f=;char c;while(!isdigit(c=getchar()))if(c=='-')f=;
while(isdigit(c))x=x*+(c&),c=getchar();return f?x=-x:x;
}
const int N=+;
struct Remilia_Scarlet{
int x,y,d;
inline bool operator <(const Remilia_Scarlet&A)const{
return d>A.d;
}
}q[N];
int A[N<<],fa[N<<];
int T,n,m,fx,fy,flag;
inline int Get(int x){return fa[x]^x?fa[x]=Get(fa[x]):x;} int main(){//freopen("test.in","r",stdin);//freopen("test.out","w",stdout);
read(T);while(T--){
read(n);m=;flag=;
for(register int i=;i<=n;++i)A[++m]=read(q[i].x),A[++m]=read(q[i].y),read(q[i].d);
sort(A+,A+m+);m=unique(A+,A+m+)-A-;sort(q+,q+n+);
for(register int i=;i<=m;++i)fa[i]=i;
for(register int i=;i<=n;++i){
if(q[i].d){
fx=Get(lower_bound(A+,A+m+,q[i].x)-A),fy=Get(lower_bound(A+,A+m+,q[i].y)-A);
if(fx^fy)fa[fx]=fy;//ddbg(fx,fy);
}
else{
fx=Get(lower_bound(A+,A+m+,q[i].x)-A),fy=Get(lower_bound(A+,A+m+,q[i].y)-A);
if(fx^fy)continue;
flag=;break;
}
}
flag?printf("NO\n"):printf("YES\n");
}
return ;
}
上一篇:Ubuntu下重新安装软件 配置文件不重新生成得问题解决


下一篇:NetBeans工具学习之道:NetBeans的(默认)快捷键