Submission #596491

#	Time	Username	Problem	Language	Result	Execution time	Memory
596491		Elias	Game (IOI14_game)	C++17	0 / 100	1 ms	308 KiB

game

#include <bits/stdc++.h>

#ifndef _DEBUG
#include "game.h"
#endif

using namespace std;

vector<int> parent; // logn union find
vector<int> remain;

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

void initialize(int n)
{
	parent = remain = vector<int>(n);
	for (int i = 0; i < n; i++)
	{
		parent[i] = i;
		remain[i] = n - 1;
	}
}

// if the remaining edge is queried, it exists, otherwise it doesn't. This guarantees there are at least 2 groups left until the end
int hasEdge(int u, int v)
{
	u = find(u);
	v = find(v);
	remain[u]--;
	remain[v]--;
	if (remain[u] == 0 || remain[v] == 0)
	{
		parent[u] = u;
		remain[v] += remain[u];
		return 1;
	}
	return 0;
}

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