Poj Solution 1628

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

#include <stdio.h>
#include <algorithm>
using namespace std;

__int64 p[210],q[210];

inline int geti( char c )
{
    if( c <= 'Z' && c >= 'A' ) return c - 'A' + 26;
    else return c - 'a';
}
int n, m;

void print( __int64 b )
{
    int i;
    
    for( i=0; i<26; i++ )
    if( b & ((__int64)1<<i) ) printf( "%c", 'a'+i );
    
    for( i=26; i<52; i++ )
    if( b & ((__int64)1<<i) ) printf( "%c", 'A'+(i-26) );

    printf( "n" );
}



void init()
{
    int i, j;
    char w1[200],w2[200];

    scanf( "%d %d", &n, &m );

    for( i=0; i<n; i++ )
    {
        scanf( "%s%*s%s", w1, w2 );
        p[i] = 0, q[i] = 0;
        
        for( j=0; w1[j]; j++ )
            p[i] |= ( (__int64)1 << geti( w1[j] ) );
        
        for( j=0; w2[j]; j++ )
            q[i] |= ( (__int64)1 << geti( w2[j] ) );

    }

}

__int64 b;


void doit()
{
    int s, i, j;
    bool key;
    char w[200];

    scanf( "%s", w );
    b = 0;
    for( j=0; w[j]; j++ )
    b |= ( (__int64)1 << geti( w[j] ) );

    for( key=true,s=n; key; )
    {
        key = false;
        
        for( i=0; i<s; i++ )
        {
            if( ( b | q[i] ) == b )
            {
                s--;
                swap( q[i], q[s] );
                swap( p[i], p[s] );
                i--;
                continue;
            }

            if( ( b | p[i] ) == b )
            {
                b |= q[i];
                key = true;
                break;
            }
        }
    }
    
    print( b );
}

int main()
{
    init();
    while( m-- )
        doit();

    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 *