3
26
2016
0

[BZOJ4423] [AMPPZ2013]Bytehattan

很久以前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;
}
Category: BZOJ | Tags: OI bzoj | Read Count: 713

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com