Submission #527644

#	Time	Username	Problem	Language	Result	Execution time	Memory
527644		sliviu	Game (IOI14_game)	C++17	100 / 100	415 ms	25188 KiB

game

#include <bits/stdc++.h>    
#include <game.h>

using namespace std;

int n;
vector<int> p, s;
vector<vector<int>> c;

void initialize(int N) {
	n = N;
	p.resize(n), s.resize(n, 1);
	iota(p.begin(), p.end(), 0);
	c.assign(n, vector<int>(n));
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < n; ++j)
			c[i][j] = i != j;
}

int get(int a) {
	if (p[a] == a)
		return a;
	return p[a] = get(p[a]);
}

void unite(int a, int b) {
	if (a == b)
		return;
	if (s[b] > s[a])
		swap(a, b);
	for (int i = 0; i < n; ++i)
		c[i][a] = (c[a][i] += c[b][i]);
	c[a][b] = c[b][a] = 0;
	s[a] += s[b];
	p[b] = a;
}

int hasEdge(int a, int b) {
	a = get(a), b = get(b);
	if (c[a][b] > 1) {
		--c[a][b], --c[b][a];
		return 0;
	}
	unite(a, b);
	return 1;
}

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