Poj Solution 3217

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

#include <stdio.h>
#include <memory.h>
#include <vector>

using namespace std;

vector<int> ch[101];
int father[101], mother[101];
bool gender[101];
int A, B;

void input( ) {
    int i, h, t;

    scanf( "%d%d", &A, &B );
    for( i=0; i<101; i++ )
        ch[i].clear( );
    
    while( true ) {
        if( scanf( "%d", &h ) != 1 )
            break;

        while( true ) {
            scanf( "%d", &t );
            if( t <= 0 ) {
                gender[h] = (t==0);
                break;
            }
            ch[h].push_back( t );
        }
        
        for( i=0; i<ch[h].size(); i++ )
            if( gender[h] )
                father[ ch[h][i] ] = h;
            else
                mother[ ch[h][i] ] = h;
    }
    return;
}

void fill( vector<int> &s, int p, int LIMIT ) {
    int a, b = 0, i, k;
    
    s.push_back( p );

    for( k=0; k<LIMIT; k++ ) {
        a = b;
        b = s.size();
        for( i=a; i<b; i++ ) {
            if( father[s[i]] )
                s.push_back( father[s[i]] );
            if( mother[s[i]] )
                s.push_back( mother[s[i]] );
        }
    }

}

void check( ) {
    int i, j;

    if( gender[A] == gender[B] ) {
        printf( "samen" );
        return;
    }

    vector<int> sa, sb;

    fill( sa, A, 2 );
    fill( sb, B, 2 );

    for( i=0; i<sa.size(); i++ ) {
        for( j=0; j<sb.size(); j++ ) {
            if( sa[i] == sb[j] ) {
                printf( "closen" );
                return;
            }
        }
    }


    sa.clear( );
    fill( sa, A, 100 );
    for( i=0; i<sa.size(); i++ )
        if( sa[i] == B ) {
            printf( "closen" );
            return;
        }

    sb.clear( );
    fill( sb, B, 100 );
    for( i=0; i<sb.size(); i++ )
        if( sb[i] == A ) {
            printf( "closen" );
            return;
        }
    printf( "marriagen" );
    return ;
}

int main( ) {
    input( );
    check( );
    return 0;
}



											
This entry was posted in poj. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *