Poj Solution 1766

http://poj.org/problem?id=1766

#include<iostream>
using namespace std;
int edge[32][32],sign[32];
int e[][2]={{0,1},{0,2},{0,3},{0,4},{0,5},
        {11,6},{11,7},{11,8},{11,9},{11,10},
        {1,2},{2,3},{3,4},{4,5},{5,1},
        {6,7},{7,8},{8,9},{9,10},{10,6},
        {1,6},{1,7},
        {2,7},{2,8},
        {3,8},{3,9},
        {4,9},{4,10},
        {5,10},{5,6},
        };
void find(int a)
{int i;
for(i=0;i<32;i++)
    if(edge[a][i]&&sign[i]==0){sign[i]=1;find(i);}
}


int main()
{int i,j,a,b,k,h,n,yes,no,past;
for(i=0;i<32;i++)
for(j=0;j<32;j++)edge[i][j]=0;

for(i=0;i<30;i++)
{a=e[i][0];b=e[i][1];edge[a][b]=edge[b][a]=1;}

h=12;
for(i=0;i<12;i++)
for(j=i+1;j<12;j++)
for(k=j+1;k<12;k++)
if(edge[i][j]&&edge[i][k]&&edge[j][k])
    {edge[h][i]=edge[i][h]=1;
     edge[h][j]=edge[j][h]=1;
         edge[h][k]=edge[k][h]=1;     
    h++;
    }

for(i=0;i<12;i++)
for(j=i+1;j<12;j++)
if(edge[i][j])
    {for(k=12;k<32;k++)
     for(h=k+1;h<32;h++)
     if(edge[i][k]&&edge[i][h]&&edge[j][k]&&edge[j][h])
     {edge[k][h]=edge[h][k]=1;}
    }

for(i=0;i<32;i++)sign[i]=0;

for(i=0;i<12;i++)
for(j=0;j<12;j++)edge[i][j]=0;
/*
for(i=0;i<32;i++)
{for(j=0;j<32;j++)
cout<<edge[i][j]<<' ';cout<<endl;}
*/

sign[12]=1;sign[13]=-1;
yes=12;no=13;past=-1;
cin>>n;

while(n--)
{cin>>a;
for(h=0;h<32;h++)if(edge[yes][h]&&edge[no][h]&&h!=past)break;
//cout<<h<<endl;        
if(a==1){sign[h]=-1;past=no;no=h;}
else {sign[h]=1;past=yes;yes=h;}
}

for(i=0;i<32;i++)
if(sign[i]==1)find(i);

int gs=0,bs=0,ws=0;
for(i=0;i<32;i++){
    if(sign[i]==1)gs++;
    else {if(i<12)bs++;
        else ws++;
        }
    }
cout<<bs<<' '<<ws<<' '<<gs<<endl;
return 0;
}
											
This entry was posted in poj. Bookmark the permalink.