Submission #171720

#	Time	Username	Problem	Language	Result	Execution time	Memory
171720		Nodir_Bobiev	Game (IOI14_game)	C++14	100 / 100	503 ms	28244 KiB

game

# include <bits/stdc++.h>
# define FILE

using namespace std;

int n,cnt[2000][2000];
int p[2000], sz[2000];

int get( int x ){
	if( p[x] == x )return x;
	else return p[x] = get( p[x] );
}
void unin( int x, int y ){
	x = get( x );
	y = get( y );
	p[x] = y;
	sz[y] += sz[x];
	for( int i = 0; i < n; i ++ ){
		cnt[y][i] += cnt[x][i];
		cnt[i][y] += cnt[x][i];
	}
}
void initialize( int m ){
	n = m;
	for( int i = 0; i < n; i ++ ){
		p[i] = i;
		sz[i] = 1;
	}
}
bool hasEdge( int u, int v ){
	int x = get( u );
	int y = get( v );
	if( sz[x] * sz[y] - cnt[x][y] == 1 ){
		unin( u,v );
		return true;
	}
	cnt[x][y] ++;
	cnt[y][x] ++;
	return false;
}
/*

int main(){

    # ifdef FILEs
        freopen( "input.txt", "r", stdin );
        freopen( "output.txt", "w", stdout );
    # endif
    ios_base::sync_with_stdio(false);
    int m;
    cin >> m;
    initialize( m );
    while( true ){
    	int a, b;
    	cin >> a >> b;
    	cout << hasEdge( a, b ) << endl;
    }
}
*/

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