Submission #652489

#	Time	Username	Problem	Language	Result	Execution time	Memory
652489		as111	Game (IOI14_game)	C++14	100 / 100	357 ms	25256 KiB

game

#include <game.h>
#include <iostream>

#define MAXN 1500

using namespace std;
int parent[MAXN + 1]; // initialize parent[i] = i

int findRoot(int a) {
	if (parent[a] == a) {
		return a;
	}
	return parent[a] = findRoot(parent[a]);
}

int available[MAXN + 1][MAXN + 1];
int N;
void initialize(int n) {
  N = n;
	for (int i = 0; i < n; i++) {
		fill(available[i], available[i] + MAXN + 1, 1);
		parent[i] = i;
	}
}

int hasEdge(int u, int v) {
	u = findRoot(u);
	v = findRoot(v);
	if (u==v) return 1; // in same cluster, doesn't matter
	//in different cluster, merge only if total available in the cluster is 1
	if (available[u][v] == 1) { // if u and v must be connected for whole graph to eventually be connected
		parent[v] = u;
		for (int i = 0; i < N; i++) {
			if (i != u && i != v && parent[i] == i) {
				available[u][i] = available[u][i] + available[v][i];
				available[i][u] = available[u][i]; // if both u and v can connect to i, wait until say no to one of them
			}
		}
		return 1; 
	}
	else { // another value in the cluster can connect to v later on, can skip for now
		available[u][v] --;
		available[v][u] --;
		return 0;
	}
}
/*
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> N;
	initialize(N);
	for (int i = 0; i < N * (N - 1) / 2; i++) {
		int u, v;
		cin >> u >> v;
		cout << hasEdge(u, v);
	}
}*/

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