这题看了PKKJ的wiki才会的,他虚设一个点Xn=0,然后就变得很方便处理了!!!
 /**//*
有n(n<=20000)个未知的整数X0,X1,X2 Xn-1,有以下Q个(Q<=40000)操作:
I p v :告诉你Xp=v
I p q v :告诉你Xp Xor Xq=v
Q k p1 p2 … pk : 询问 Xp1 Xor Xp2 .. Xor Xpk, k不大于15。
如果当前的I跟之前的有冲突的话,跳出

并查集扩展!
对于I p v ,如果虚设一个点Xn=0,则可以看成 I p n v (与0异或)
所以对于所有那些I,都是a^b=v,两个两个的,连带的效果
所以设val[i]=Xi^Xfa[i] 跟上面一样有连带效果 fa[i]为i的父亲
这样:
1) I p q v
先find
如果p q在同一集合,判断是否有Xp^Xq=v 不是的话矛盾
否则,合并 注意虚设的点n要始终保持为根
2)Q k p1 pk
Xp1 ^ Xp2 ^ Xpk
转化为:
val[p1] ^ val[p2] ^ val[k] ^ (Xfa[p1] ^ Xfa[p2] ^ Xfa[pk])
val[pi]已知,只需判断Xfa[pi]是否已知
由于是异或,奇数个Xfa[pi]才需判断。判断方法为看他的根是不是Xn即可
*/
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>

using namespace std;

const int MAXN = 20010;

int fa[MAXN],val[MAXN];
int n,q;

void init(int n)
  {
for(int i=0;i<=n;i++)
 {
val[i]=0;
fa[i]=i;
}
}
int find(int a)
  {
if(a!=fa[a])
 {
int t=fa[a];
fa[a]=find(fa[a]);
val[a]^=val[t];
}
return fa[a];
}

bool unin(int a,int b,int v)
  {
int ra=find(a);
int rb=find(b);
if(ra==rb)
 {
return v==(val[a]^val[b]);
}
if(ra==n)swap(ra,rb);
fa[ra]=rb;
val[ra]=val[a]^val[b]^v;
return true;
}

char cmd[MAXN];

int main()
  {
//freopen("in","r",stdin);
int t=1;
while(scanf("%d%d",&n,&q),n)
 {
printf("Case %d:\n",t++);
init(n);
int fact = 0;
bool err = false;
for(int i=0;i<q;i++)
 {
scanf(" %c",&cmd[0]);
 if(err) {gets(cmd);continue;}
if(cmd[0]=='I')
 {
gets(cmd);//需要这样子
fact++;
int x,y,v;
if(sscanf(cmd,"%d%d%d",&x,&y,&v)==2)//sscanf() 直接scanf()会错 不知为啥
 {
swap(y,v);
y=n;
}
if(!unin(x,y,v))
 {
err = true;
printf("The first %d facts are conflicting.\n",fact);
}
}
else
 {
int k,x,ans=0;
vector<pair<int,int> >V;
scanf("%d",&k);
for(int j=0,jj;j<k;j++)
 {
scanf("%d",&x);
int rx = find(x);
ans^=val[x];
for(jj=0;jj<V.size();jj++)
 {
if(V[jj].first==rx)break;
}
if(jj==V.size())V.push_back(make_pair(rx,1));
else V[jj].second^=1;
}
bool flag = true;
for(int j=0;j<V.size();j++)
 {
if(V[j].second)
 {
int rx=find(V[j].first);
 if(rx!=n) {flag=false;break;}
ans^=val[V[j].first];
}
}
if(flag)printf("%d\n",ans);
else puts("I don't know.");
}
}
puts("");
}
return 0;
}
|
|
常用链接
随笔分类
Links
搜索
最新评论

|
|