Cod sursa(job #214830)

Utilizator devilkindSavin Tiberiu devilkind Data 16 octombrie 2008 11:55:43
Problema A+B Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.52 kb
#include <stdio.h>
#include <vector>

using namespace std;

#define NMAX 1024
#define KMAX 4020
#define pb push_back
#define sz size()

int N, M, K;
vector<int> G[2*NMAX];
vector<int> sol;
int ST[2*NMAX];
int X[KMAX], Y[KMAX];
int SW[NMAX][NMAX], IND[NMAX][NMAX];

int BF(int nod)
{
     int viz[NMAX];
     int cd[NMAX];
     int TT[NMAX];
     int i, j, x, y;
     
     memset(viz, 0, sizeof(viz));
     viz[nod] = 1;
     
     cd[0] = 1;
     cd[1] = nod;
     
     for (i = 1; i <= cd[0]; i++)
               for (j = 0; j < G[ cd[i] ].sz; j++)
                   if (!viz[ G[ cd[i] ][j] ]) 
                      {
                             cd[ ++cd[0] ] = G[ cd[i] ][j];
                             viz[ G[ cd[i] ][j] ] = 1;                             
                             TT[ G[ cd[i] ][j] ] = cd[i];
                      }
                      
     for (i = 1; i < N+M; i++)                      
         if (i != nod && ST[i] && viz[i]) 
                  {
                      j = i;                  
                      while (j != nod)
                            {
                               x = j;
                               y = TT[j];
                               
                               if (x >= N) SW[y][x-N+1]=!SW[y][x-N+1];
                                  else SW[x][y-N+1]=!SW[x][y-N+1];
                                  
                               j=TT[j];                            
                            }
                      
                      ST[nod]=0;
                      ST[i]=0;
                      return 1;
                  }
     return 0;
}

void solve()
{
     int i, j, x, y;
     
     scanf("%d %d %d", &N, &M, &K);
              
     for (i = 1; i < N; i++)
     {
         scanf("%d ", &x);         
         ST[i] = x;
     }
    
     for (i = 1; i < N; i++)
     {
         scanf("%d ", &x);         
         ST[i] = (ST[i]^x);
     }
        
     for (i = 0; i < M-1; i++)
     {
         scanf("%d ", &x);         
         ST[ N+i ] = x;
     }
    
     for (i = 0; i < M-1; i++)
     {
         scanf("%d ", &x);         
         ST[ N+i ] = (ST[ N+i ]^x);
     }
     
     for (i = 0; i < K; i++)         
         scanf("%d ", &X[i]);
         
     for (i = 0; i < K; i++)         
         scanf("%d ", &Y[i]);
         
     for (i = 0; i < K; i++)
     {
         G[ X[i] ].pb(N+Y[i]-1);         
         G[ N+Y[i]-1 ].pb(X[i]);
         IND[ X[i] ][ Y[i] ] = i;     
     }
     
 //    for (i = 1; i < N+M; i++) 
   //      printf("%d ",ST[i]);
 
     int ok=1;        
     for (i = 1; i < N+M; i++)
         if (ST[i]) 
            {
                    ok=BF(i);
                    if (!ok) 
                       {
                       printf("-1\n");
                       return;
                       }
            }
            
     for (i = 1; i <= N; i++)
         for (j = 1; j <= M; j++)
             if (SW[i][j]) sol.pb(IND[i][j]);

     printf("%d ",sol.sz);
     for (i = 0; i < sol.sz; i++)
         printf("%d ", sol[i]);
     printf("\n");
}


int main()
{
    freopen("switch.in", "r", stdin);
    freopen("switch.out", "w", stdout);

    int T;    
    for (scanf("%d ", &T); T; T--)
    {               
        solve();
        
        for (int i = 1; i <= N+M; i++)    
              G[i].clear();
              
        memset(SW, 0, sizeof(SW) );
        sol.clear();
    }
    return 0;
}