Submission #779338

#	Time	Username	Problem	Language	Result	Execution time	Memory
779338		Sohsoh84	Game (IOI14_game)	C++17	100 / 100	352 ms	41124 KiB

game

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

using namespace std;

#define all(x)		(x).begin(),(x).end()

const int MAXN = 3000 + 10;

int n, f[MAXN][MAXN], id[MAXN], par[MAXN], sz[MAXN], dsz = 0;

void initialize(int n_) {
	n = n_;
	for (int i = 1; i <= n; i++) {
		id[i] = par[i] = i;
		sz[i] = 1;
	}

	dsz = n;
}

inline int find(int v) {
	return par[v] == v ? v : par[v] = find(par[v]);
}

inline void unite(int u, int v) {
	u = find(u), v = find(v);
	if (u == v) return;
	
	for (int i = 1; i <= dsz; i++)
		f[dsz + 1][i] = f[i][dsz + 1] = f[id[u]][i] + f[id[v]][i];

	par[v] = u;
	sz[u] += sz[v];
	id[u] = ++dsz;
}

int hasEdge(int u, int v) {
	u++;
	v++;

	if (f[id[find(u)]][id[find(v)]] == sz[find(u)] * sz[find(v)] - 1) {
		unite(u, v);
		return 1;
	}

	f[id[find(u)]][id[find(v)]]++;
	f[id[find(v)]][id[find(u)]]++;
	return 0;
}

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