# 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.