Submission #596536

#	Time	Username	Problem	Language	Result	Execution time	Memory
596536		Elias	Game (IOI14_game)	C++17	100 / 100	451 ms	25268 KiB

game

#include <bits/stdc++.h>

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

using namespace std;

vector<int> parent; // logn union find
vector<vector<int>> queried;
int n;

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

void initialize(int n)
{
	::n = n;
	parent = vector<int>(n);
	queried = vector<vector<int>>(n, vector<int>(n));
	for (int i = 0; i < n; i++)
	{
		parent[i] = i;
	}
}

int hasEdge(int u, int v)
{
	queried[u][v] = 1;
	queried[v][u] = 1;

	int U = find(u);
	int V = find(v);

	if (U > V)
		swap(U, V), swap(u, v);

	bool a = U == 0;
	int b = V == 0;

	if (a ^ b)
	{
		for (int i = 0; i < n; i++) // only insert edge if last query to group zero
			if (find(i) == 0 && !queried[v][i])
				return 0;

		parent[V] = 0;
		assert(U == 0);
		return 1;
	}
	return 0;
}

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