Submission #299825

#	Time	Username	Problem	Language	Result	Execution time	Memory
299825		dCoding	Game (IOI14_game)	C++17	0 / 100	1 ms	384 KiB

game

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

const int MAXN = 1505;
int comps;
int n;
int called;
int root[MAXN], ranks[MAXN];

int findRoot(int node) {
	if(root[node] == node) return node;
	return root[node] = findRoot(root[node]);
}

bool sameComp(int u, int v) {
	return findRoot(u) == findRoot(v);
}

bool unite(int u, int v) {
	if(sameComp(u,v)) return false;
	int r1 = findRoot(u);
	int r2 = findRoot(v);
	if(ranks[r1] >= ranks[r2]) {
		root[r2] = r1;
		ranks[r1] += ranks[r2];
	} else { 
		root[r1] = r2;
		ranks[r2] += ranks[r1];
	}
	return true;
}

void initialize(int _n) {
	n = _n;
	comps = n;
	for(int i=0;i<n;i++) {
		root[i] = i;
		ranks[i] = 1;
	}
}

int hasEdge(int u, int v) {
	++called;
	if(sameComp(u,v)) {
		return 1;
	}
	if(called == (n*(n-1))/2) {
		assert(comps == 2);
		return 1;
	}
	if(comps == 2) return 0;
	unite(u,v);
	--comps;
	return 1;
}

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