Submission #30445

#	Time	Username	Problem	Language	Result	Execution time	Memory
30445		Nikefor	Game (IOI14_game)	C++98	100 / 100	723 ms	18716 KiB

game

#include "game.h"
#include <cstdio>
int con[1501][1501];
int siz[1501];
int rep[1501];
int N;
int findrep(int n) {
	while(n!=rep[n]) n = rep[n];
	return n;
}
void initialize(int n) {
	N = n;
	for(int i=0; i<=n; i++) {
		siz[i] = 1;
		rep[i] = i;
	}
}

int hasEdge(int u, int v) {

	int x = findrep(u);
	int y = findrep(v);
    if(con[x][y] != siz[x]*siz[y]-1) {
    	con[x][y]++;
    	con[y][x]++;
    	return 0;
    }
    //merge u and v
    rep[y] = x;
    siz[x]+=siz[y];
    for (int i = 0; i < N; ++i) {
    	con[x][i]+=con[y][i];
    	con[i][x]+= con[y][i];
    }
    return 1;


}

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