Submission #48328

#	Time	Username	Problem	Language	Result	Execution time	Memory
48328		wijw111	Game (IOI14_game)	C++14	100 / 100	490 ms	19084 KiB

game

#include "game.h"

const int N = 2000;
int p[N], c[N], cnt[N][N], pn;

int find(int a){
	return p[a] == a ? a : (p[a] = find(p[a]));
}

void merge(int a, int b){
	p[b] = p[a];
	c[a] += c[b];

	for(int i=0; i<pn; i++){
		cnt[a][i] += cnt[b][i];
		cnt[i][a] += cnt[i][b];
	}
}

void initialize(int n) {
	pn = n;

	for(int i=0; i<pn; i++){
		p[i] = i;
		c[i] = 1;
	}
}

int hasEdge(int u, int v) {
	u = find(u);
	v = find(v);

	cnt[u][v]++;
	cnt[v][u]++;

	if(cnt[u][v] == c[u]*c[v]){
		merge(u, v);
		return 1;
	}

   return 0;
}

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