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);
}
訂閱:
張貼留言 (Atom)
沒有留言:
張貼留言