Submission #106447

#	Time	Username	Problem	Language	Result	Execution time	Memory
106447		Nodir_Bobiev	Game (IOI14_game)	C++14	100 / 100	730 ms	22588 KiB

game

# include <iostream>

using namespace std;

int N;
int p[2000];
int quan[2000];
int cnt[2000][2000];

int get( int x )
{
	if( p[x] == x )
		return x;
	else
		return p[x] = get( p[x] );
}

void unin( int x, int y )
{
	for ( int i = 1; i <= N; i ++ ){
		if ( i != x ){
			cnt[i][x] += cnt[i][y];
			cnt[x][i] += cnt[i][y];
		}
	}
	quan[x] += quan[y];
	p[y] = x;
}

void initialize( int n )
{
	N = n;
	for ( int i = 1; i <= N; i ++ )
		p[i] = i;
	
	for ( int i = 1; i <= N; i ++ )
		quan[i] = 1;
}

int hasEdge( int v, int u )
{	
	int x = v + 1;
	int y = u + 1;
	
	x = get( x );
	y = get( y );
	
	if ( x == y )
		return 0;
			
	if ( quan[x] * quan[y] - cnt[x][y] == 1 ){
		unin( x, y );
		return 1;
	}
	
	else{
		cnt[x][y] ++;
		cnt[y][x] ++;
		return 0;
	}
}

• Subtask 1: 15 / 15
• Subtask 2: 27 / 27
• Subtask 3: 58 / 58