Submission #106472

#	Time	Username	Problem	Language	Result	Execution time	Memory
106472		tincamatei	Game (IOI14_game)	C++14	100 / 100	712 ms	15992 KiB

game

#include "game.h"

const int MAX_N = 1500;

int sef[MAX_N];
int edges[MAX_N][MAX_N];
int size[MAX_N];

int N;

int myfind(int x) {
	if(x == sef[x])
		return x;
	sef[x] = myfind(sef[x]);
	return sef[x];
}

void myunion(int a, int b) {
	int sa, sb;
	sa = myfind(a);
	sb = myfind(b);

	sef[sb] = sa;
	
	if(sa != sb) {
		edges[sa][sb] = edges[sb][sa] = 0;
		for(int i = 0; i < N; ++i) {
			edges[sa][i] += edges[sb][i];
			edges[i][sa] += edges[i][sb];
		}
	
		size[sa] += size[sb];
	}
}

void initialize(int n) {
	N = n;
	for(int i = 0; i < n; ++i) {
		sef[i] = i;
		size[i] = 1;
	}
}

int hasEdge(int u, int v) {
	int su, sv;

	su = myfind(u);
	sv = myfind(v);

	edges[su][sv]++;
	edges[sv][su]++;

	if(edges[su][sv] == size[su] * size[sv]) {
		myunion(su, sv);
		return 1;
	} else
		return 0;
}

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