Submission #113994

#	Time	Username	Problem	Language	Result	Execution time	Memory
113994		E869120	Game (IOI14_game)	C++14	100 / 100	511 ms	25376 KiB

game

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

// ------------------------ LIBRARY START

int t[1509], sz[1509], cnt[1509][1509];

void init() {
	for (int i = 0; i < 1500; i++) { t[i] = i; sz[i] = 1; }
}

void add_edge(int u, int v) {
	cnt[t[u]][t[v]]++; cnt[t[v]][t[u]]++;
}

bool same(int u, int v) {
	if (t[u] == t[v]) return true;
	return false;
}

void unite(int u, int v) {
	u = t[u]; v = t[v];
	for (int i = 0; i < 1500; i++) {
		if (i == u || i == v) continue;
		cnt[u][i] += cnt[v][i]; cnt[v][i] = 0;
		cnt[i][u] += cnt[i][v]; cnt[i][v] = 0;
	}
	cnt[u][v] = 0;
	
	for (int i = 0; i < 1500; i++) {
		if (t[i] == v) { t[i] = u; sz[v]--; sz[u]++; }
	}
}

// ------------------------ LIBRARY END

int N;

void initialize(int n) {
	N = n; init();
}

int hasEdge(int u, int v) {
	//cout << "# " << sz[t[u]] << " " << sz[t[v]] << " "<< cnt[t[u]][t[v]] << endl;
	if (sz[t[u]] * sz[t[v]] - 1 == cnt[t[u]][t[v]]) {
		unite(u, v);
		return 1;
	}
	add_edge(u, v);
    return 0;
}

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