Submission #48236

#	Time	Username	Problem	Language	Result	Execution time	Memory
48236		cheater2k	Game (IOI14_game)	C++17	0 / 100	2 ms	840 KiB

game

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

const int MAXN = 1505;

int n, par[MAXN], nver[MAXN], nedge[MAXN];

int anc(int p) { return p == par[p] ? p : par[p] = anc(par[p]); }
bool join(int p, int q) {
	p = anc(p), q = anc(q);
	++nedge[p];
	++nedge[q];

	if (nedge[p] == nver[p] * (n - nver[p]) || nedge[q] == nver[q] * (n - nver[q])) {
		// join p, q
		nedge[p] -= nver[p] * nver[q];
		nedge[q] -= nver[p] * nver[q];
		nedge[q] += nedge[p]; nedge[p] = 0;
		nver[q] += nver[p]; nver[p] = 0;
		par[p] = q;
		return true;
	} else {
		return false;
	}
}

void initialize(int N) {
	n = N;
	for (int i = 0; i < n; ++i) {
		par[i] = i;
		nver[i] = 1;
		nedge[i] = 0;
	}
}

int hasEdge(int u, int v) {
	return join(u, v);
}

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