很久以前wzf出给我们的题目。。。
考虑加边，每次并查集加完只要并查集内联通就说明实际堵塞
不联通就说明实际联通
#include<cstdio>
int n,k,ans=1,f[10000005];
int Find(int x){
return x==f[x]?f[x]:f[x]=Find(f[x]);
}
void Union(int sa,int sb){
if(sa>sb)f[sa]=sb;
else f[sb]=sa;
}
int Get(int x,int y){
if(x==n || y==n || x==0 || y==0)return 0;
return (x-1)*n+y;
}
int main(){
freopen("4423.in","r",stdin);
freopen("4423.out","w",stdout);
scanf("%d %d",&n,&k);
for(int i=1;i<=n*n+n;i++)f[i]=i;
while(k--){
int sa1,sb1,sa2,sb2;
char w1[5],w2[5];
scanf("%d %d %s %d %d %s",&sa1,&sb1,w1,&sa2,&sb2,w2);
if(ans==0){sa1=sa2;sb1=sb2;w1[0]=w2[0];}
if(w1[0]=='N'){
if(Find(Get(sa1,sb1))!=Find(Get(sa1-1,sb1))){Union(Find(Get(sa1,sb1)),Find(Get(sa1-1,sb1)));ans=1;}
else ans=0;
}
else {
if(Find(Get(sa1,sb1))!=Find(Get(sa1,sb1-1))){Union(Find(Get(sa1,sb1)),Find(Get(sa1,sb1-1)));ans=1;}
else ans=0;
}
if(ans)puts("TAK");
else puts("NIE");
}
return 0;
}
评论 (0)
