Submission #385421

#	Time	Username	Problem	Language	Result	Execution time	Memory
385421		alireza_kaviani	Game (IOI14_game)	C++11	100 / 100	513 ms	23936 KiB

game

#include <bits/stdc++.h>
#include "game.h"
using namespace std;

const int MAXN = 2000;
int cnt[MAXN][MAXN] , par[MAXN] , sz[MAXN];

void initialize(int n) {
	for(int i = 0 ; i < MAXN ; i++){
		fill(cnt[i] , cnt[i] + MAXN , 1);
		par[i] = -1; sz[i] = 1;
	}
}

int Find(int v){
	return (par[v] == -1 ? v : par[v] = Find(par[v]));
}

void Union(int v , int u){
	v = Find(v); u = Find(u);
	if(sz[v] < sz[u])	swap(v , u);
	par[u] = v; sz[v] += sz[u];
	for(int i = 0 ; i < MAXN ; i++){
		cnt[v][i] += cnt[u][i];
		cnt[i][v] += cnt[i][u];
	}
}

int hasEdge(int u, int v) {
	u = Find(u); v = Find(v);
	cnt[u][v]--; cnt[v][u]--;
	if(cnt[v][u] > 0)	return 0;
	Union(v , u);
	return 1;
}

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