Submission #52022

#	Time	Username	Problem	Language	Result	Execution time	Memory
52022		radoslav11	Game (IOI14_game)	C++14	100 / 100	634 ms	169672 KiB

game

#include <bits/stdc++.h>
#include "game.h"
//#include "Lgrader.cpp"

using namespace std;
template<class T, class T2> inline int chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline int chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const int MAXN = (1 << 12);

int cnt[MAXN][MAXN], par[MAXN];
void init(int n) { for(int i = 0; i <= n; i++) par[i] = i; }
int root(int x) { return par[x] = (par[x] == x ? x : root(par[x])); }

int n;

void initialize(int n) 
{
	::n = n;
	init(n);

	for(int i = 0; i < n; i++)
		for(int j = 0; j < n; j++)
			cnt[i][j] = 1;
}

int hasEdge(int u, int v) 
{
	u = root(u), v = root(v);
	if(u == v) return 1;

	if(cnt[u][v] > 1)
	{
		cnt[u][v]--;
		cnt[v][u]--;
		return 0;
	}

	par[v] = u;
	for(int x = 0; x < n; x++)
		if(x == root(x) && x != u)
			cnt[u][x] = cnt[x][u] = cnt[u][x] + cnt[v][x];

	return 1;
}

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