Submission #678001

#	Time	Username	Problem	Language	Result	Execution time	Memory
678001		Hacv16	Game (IOI14_game)	C++17	100 / 100	348 ms	25492 KiB

game

#include <bits/stdc++.h>
#include "game.h"
using namespace std;
 
const int MAX = 1550;
 
int n, pai[MAX], sze[MAX], f[MAX][MAX];

int find(int u){
	return pai[u] = (pai[u] == u ? u : find(pai[u]));
}

void join(int u, int v){
	u = find(u), v = find(v);
	if(u == v) return;

	if(sze[v] > sze[u]) swap(u, v);
	pai[v] = u; sze[u] += sze[v];

	for(int i = 1; i <= n; i++)
		f[u][i] += f[v][i], f[i][u] += f[v][i];
}

void initialize(int _n){
	n = _n;

	for(int i = 1; i <= n; i++){
		pai[i] = i; sze[i] = 1;

		for(int j = i + 1; j <= n; j++)
			f[i][j] = f[j][i] = 1;
	}
}
 
int hasEdge(int u, int v){
	u++, v++;

	u = find(u), v = find(v);
	if(u == v) return 0;

	if(f[u][v] == 1){ join(u, v); return 1; }
	f[u][v]--, f[v][u]--;

	return 0;
}

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