Submission #234688

#	Time	Username	Problem	Language	Result	Execution time	Memory
234688		Fischer	Game (IOI14_game)	C++14	100 / 100	522 ms	25336 KiB

game

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1510 + 10;
int rnk[maxn];
int link[maxn];
int cnt[maxn][maxn];
int n;

int get(int x) {
	if (x == link[x]) {
		return x;
	}
	return link[x] = get(link[x]);
}

void initialize(int n) {
	::n = n;
	for (int i = 1; i <= n; ++i) {
		link[i] = i;
		rnk[i] = 1;
	}
}

int hasEdge(int u, int v) {
	u += 1; v += 1;
	u = get(u); v = get(v);
	if (u == v) return 1;
	cnt[u][v] +=1;
	cnt[v][u] += 1;
	if (cnt[u][v] < rnk[u] * rnk[v]) return 0;
    if (rnk[u] < rnk[v]) swap(u, v);
    rnk[u] += rnk[v];
    link[v] = u;
    for (int i = 1; i <= n; ++i) {
    	cnt[i][u] += cnt[i][v];
    	cnt[u][i] += cnt[v][i];
    }
    return 1;
}

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