Submission #119364

#	Time	Username	Problem	Language	Result	Execution time	Memory
119364		Mamnoon_Siam	Game (IOI14_game)	C++17	100 / 100	831 ms	25464 KiB

game

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

const int maxn = 1.5e3 + 5;

int N;
int par[maxn];
int g[maxn][maxn];

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

void initialize(int n) {
	N = n;
	for(int i = 0; i < N; i++) {
		par[i] = i;
	}
	for(int i = 0; i < N; i++) {
		for(int j = 0; j < N; j++) {
			g[i][j] = 1;
		}
	}
}

int hasEdge(int u, int v) {
	int uu = find(u);
	int vv = find(v);
	if(g[uu][vv] == 1) {
		set<int> st;
		for(int i = 0; i < N; i++) {
			st.insert(find(i));
		}
		st.erase(uu);
		st.erase(vv);
		for(int i : st) {
			g[i][uu] += g[i][vv];
			g[uu][i] += g[vv][i];
		}
		g[uu][vv]--;
		g[vv][uu]--;
		par[vv] = uu;
		return 1;
	} else {
		g[uu][vv]--;
		g[vv][uu]--;
		return 0;
	}
}

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