Submission #427442

#	Time	Username	Problem	Language	Result	Execution time	Memory
427442		frodakcin	Game (IOI14_game)	C++17	100 / 100	588 ms	18676 KiB

game

#include "game.h"
#include <cassert>
#include <cstring>
#include <algorithm>
#include <vector>

const int MN = 1.5e3+10;

bool ask[MN][MN];
int p[MN], r[MN];
std::vector<int> a[MN];

int find(int n) {return p[n]==-1?n:p[n]=find(p[n]);}

bool merge(int u, int v)
{
	//u=find(u), v=find(v); //unnecessary
	if(u==v) return 0;
	if(r[u]<r[v]) std::swap(u, v);
	r[u] += r[u] == r[v];
	p[v] = u, r[v] = -1;
	if(a[u].size() < a[v].size()) a[u].swap(a[v]);
	a[u].insert(a[u].end(), a[v].begin(), a[v].end());
	a[v].clear();
	return 1;
}

void initialize(int n) {
	memset(p, -1, n*sizeof*p);
	for(int i=0;i<n;++i)
		a[i].push_back(i);
}

int hasEdge(int u, int v) {
	ask[u][v]=ask[v][u]=1;
	u=find(u), v=find(v);
	assert(u!=v);
	for(int x:a[u])
		for(int y:a[v])
			if(!ask[x][y])
				return 0;
	merge(u, v);
	return 1;
}

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