Cod sursa(job #25217)

Utilizator ViksenVictor-Nicolae Savu Viksen Data 4 martie 2007 11:27:49
Problema Balanta Scor 20
Compilator cpp Status done
Runda preONI 2007, Runda 3, Clasa a 10-a Marime 1.81 kb
#include <stdio.h>
#include <string.h>
#define max 0x7FFFFFFF

unsigned long N[1000] , M [1000] , A[1000] , B[1000];
int n,m,i,j,x,y,r,k,rn,rm;

void Extract ( unsigned long *A , unsigned long *B )
{
    int i;
    for ( i=1 ; i<=n ; i<<=5 )
       A[i>>5] &= (max - B[i>>5]) ;
}

void Deny ( unsigned long *A , unsigned long *B )
{
    int i;
    for ( i=1 ; i<=n ; i<<=5 )
       A[i>>5]&=B[i>>5];
}

void count ( unsigned long *A , int &x , int &k )
{
    int i;
    for ( i=1 ; i<=n ; i++ ) 
        if ((A[i>>5]>>(i&31))&1) x++ , k = i;
}

int main ()
{
 	freopen ( "balanta.in" , "r" , stdin );
    scanf ( "%d %d" , &n , &m );
    memset ( N , max , sizeof ( int )*((n>>5)+1) );
    memset ( M , max , sizeof ( int )*((n>>5)+1) );
    for ( i=0 ; i<m ; i++ ) {
       scanf ( "%d" , &x );
       memset ( A , 0 , sizeof ( int ) * ((n>>5)+1) );
       memset ( B , 0 , sizeof ( int ) * ((n>>5)+1) );
       for ( j=0 ; j<x ; j++ ) {
           scanf ( "%d" , &r );
           A[r>>5]|=1<<(r&31);
       }
       for ( j=0 ; j<x ; j++ ) {
           scanf ( "%d" , &r );
           B[r>>5]|=1<<(r&31);
       }
       scanf ( "%d" , &k );
       if ( k == 0 ) {
           Extract ( N , A );
           Extract ( N , B );
           Extract ( M , A );
           Extract ( M , B );
       }
       if ( k == 1 ) {
           Deny ( N , A );
           Deny ( M , B );
       }
       if ( k==2 ) {
           Deny ( M , A );
           Deny ( N , B );
        }
    }
	x=0;y=0;rn=0;rm=0;
    count ( N , x , rn );
    count ( M , y , rm );
    freopen ( "balanta.out" , "w" , stdout );
    if ( !( ((x==1)&&(y==0))||((x==0)&&(y==1)) ) ) printf (  "0\n" ) ; else
        if ( x==1 ) printf ( "%d\n" , rn ) ; else printf ( "%d\n" , rm );
    fclose ( stdout );
    return 0;
}