2014年3月6日 星期四

[HOJ] 239 - Color


#include<stdio.h>
#define N 1000005
#define M 1000000000
struct P{
    int x,y,z;
}s[N];
int p[N*4]={0},n,m,k;
int find(int k){
    if(p[k]==k) return p[k];
    return p[k]=find(p[k]);
}
int uni(int x,int y){
    //printf("%d,%d,\n",x,y);
    x=find(x);
    y=find(y);
    if(x!=y)
        p[x]=y;
    //else puts("/////");
}
int calc(){
    int i,add=1,a,b,len=n+m,tmp=0,p0=len*2+1,p1=len*2+2,x;
    for(i=1;i<=len*2+2;i++)
        p[i]=i;
    for(i=0;i<k;i++){
        if(s[i].x+s[i].y==2) continue;
        a=s[i].x;
        b=n+s[i].y;

        if(s[i].x==1 || s[i].y==1){
            if(s[i].x==1) x=b;
            else x=a;
            if(s[i].z){
                uni(x,p1),uni(x+len,p0);
                //puts("--");
            }
            else{
                uni(x,p0),uni(x+len,p1);
                //puts("++");
            }
        }
        else{
            if((((s[i].x|s[i].y)&1)^1)==s[i].z){
                uni(a,b),uni(a+len,b+len);
                //puts("-");
            }
            else{
                uni(a+len,b),uni(a,b+len);
                //puts("+");
            }
        }
    }
    for(i=2;i<=n+m;i++){
        if(i==n+1) continue;
        if(i==n+m+1) continue;
        if(i==n+m+n+1) continue;
        if(find(i)==find(len+i)) return 0;
    }
    for(i=2;i<=n+m+len+2;i++){
        if(i==n+1) continue;
        if(i==n+m+1) continue;
        if(i==n+m+n+1) continue;
        if(find(i)==i) tmp++/*,printf("%d,",i)*/;
    }
    for(i=1;i<tmp/2;i++)
        add=(add*2)%M;
    //printf("%d...",add);
    return add;
}
int main(){
    int ans=0;
    int i,flag=2;
    scanf("%d%d%d",&n,&m,&k);
    for(i=0;i<k;i++){
        scanf("%d%d%d",&s[i].x,&s[i].y,&s[i].z);
        if(s[i].x==1 && s[i].y==1){
            if(flag!=2 && flag!=s[i].z){
                puts("0");
                return 0;
            }
            flag=s[i].z;
        }
    }
    if(flag!=1) ans=calc();
    if(flag!=0){
        for(i=0;i<k;i++)
            s[i].z^=1;
        ans+=calc();
    }
    printf("%d\n",ans%M);
}

沒有留言:

張貼留言