Source

Problem Id:1628  User Id:IceAngel 
Memory:164K  Time:1015MS
Language:C++  Result:Time Limit Exceed

Source 

#include "iostream.h"
#include "string.h"
#include "stdlib.h"

#define max1 1100
#define max2 110

char graph1[max1][max2];
char graph2[max1][max2];
char map[max1][max2];
char flag[max1];
char str[max2];

int compare( const void * a , const void * b )
{
	int x = (int)(*(char*)a);
	int y = (int)(*(char*)b);

	if( x >= (int)'A' && x <= (int)'Z' )
		x += 40;
	if( y >= (int)'A' && y <= (int)'Z' )
		y += 40;
	
	return x - y;
}
bool strSub( int i , int k )
{
	int a , b;
	bool f;
	for( a = 0 ; a < (int)strlen( graph1[i] ) ; a++ )
	{
		f = false;
		for( b = 0 ; b < (int)strlen( map[k] ) ; b++ )
			if( graph1[i][a] == map[k][b] )
			{
				f = true;
			}
		if( !f )
			return false;
	}
	return true;
}
void strAdd( int k , int i )
{
	bool f;
	int a , b , c = strlen( map[k] );

	for( a = 0 ; a < (int)strlen( graph2[a] ) ; a++ )
	{
		f = true;
		for( b = 0 ; b < c ; b++ )
		{
			if( graph2[i][a] == map[k][b] )
			{
				f = false;
				break;
			}
		}
		if( f )
		{
			map[k][c++] = graph2[i][a];
		}
	}
	map[k][c] = 0;
}
int main()
{
	bool breakFlag;
	int m , n;
	int i , k;

	cin >> m >> n;
	for( i = 0 ; i < m ; i++ )
		cin >> graph1[i] >> str >> graph2[i];
	for( i = 0 ; i < n ; i++ )
		cin >> map[i];

	for( k = 0 ; k < n ; k++ )
	{
		for( i = 0 ; i < m ; i++ )
			flag[i] = 0;
		do
		{
			breakFlag = true;
			for( i = 0 ; i < m ; i++ )
			{
				if( strSub( i , k ) && flag[i] == 0 )
				{
					flag[i] = 1;
					strAdd( k , i );
					breakFlag = false;
				}
			}
		}while( !breakFlag );
		qsort( map[k] , strlen( map[k] ) , sizeof( char ) , compare );
		cout<<map[k]<<endl;
	}
	return 0;
}

• nobody knows (2038) frkstyc 2005-05-24 19:39:18
  • Re:nobody knows (5) IceAngel 2005-05-24 20:27:16
    • What I said is true. Nobody could tell whether your program is correct is you receive a TLE. (9) frkstyc 2005-05-24 20:28:08