首页 > 代码库 > [51nod1515]明辨是非
[51nod1515]明辨是非
Description
给组操作,每组操作形式为.
当时,如果第变量和第个变量可以相等,则输出,并限制他们相等;否则输出,并忽略此次操作.
当时,如果第变量和第个变量可以不相等,则输出,并限制他们不相等;否则输出,并忽略此次操作.
Input
输入一个数表示操作的次数.接下来行每行三个数.
Output
对于行操作,分别输出行或者.
Sample Input
3 1 2 1 1 3 1 2 3 0
Sample Output
YES YES NO
HINT
.
Solution
离散化所有的变量.
可以用并查集维护相等的关系,维护不等的关系.
当时,如果都不在对方的中,则可行,按大小合并它们的父亲和;
当时,如果,把分别插入对方的中.
#include<set> #include<cmath> #include<ctime> #include<queue> #include<stack> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define N 200005 using namespace std; int a[N],f[N],x[N],y[N],p[N],n,m; set<int> s[N]; set<int>::iterator l; inline int gf(int k){ if(f[k]==k) return k; return f[k]=gf(f[k]); } inline int search(int k){ int l=1,r=m,mid; while(l<r){ mid=(l+r)>>1; if(a[mid]<k) l=mid+1; else r=mid; } return l; } inline void init(){ scanf("%d",&n); for(int i=1;i<=n;++i){ scanf("%d%d%d",&x[i],&y[i],&p[i]); a[++m]=x[i];a[++m]=y[i]; } sort(a+1,a+1+m); for(int i=1;i<=n;++i){ x[i]=search(x[i]); y[i]=search(y[i]); } for(int i=1;i<=m;++i) f[i]=i; for(int i=1,j,k,q;i<=n;++i){ j=gf(f[x[i]]);k=gf(f[y[i]]); if(!p[i]){ if(j==k) puts("NO"); else{ puts("YES"); s[j].insert(k); s[k].insert(j); } } else{ if(j==k) puts("YES"); else if(s[j].count(k)||s[k].count(j)) puts("NO"); else{ puts("YES"); if(s[j].size()>s[k].size()){ q=j;j=k;k=q; } f[j]=k; for(l=s[j].begin();l!=s[j].end();++l){ q=gf(*l); s[*l].erase(j); s[q].insert(k); s[k].insert(q); } s[j].clear(); } } } } int main(){ freopen("judge.in","r",stdin); freopen("judge.out","w",stdout); init(); fclose(stdin); fclose(stdout); return 0; }
[51nod1515]明辨是非
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。