Submission #1062851

#	Time	Username	Problem	Language	Result	Execution time	Memory
1062851		Nonoze	Game (IOI14_game)	C++17	100 / 100	265 ms	24724 KiB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back
#define sz(x) (int)x.size()
#define fi first
#define se second
#define cmin(a, b) a=min(a, b)
#define cmax(a, b) a=max(a, b)

int n;
vector<int> sz, par;
vector<vector<int>> comp;
set<int> compo;

void initialize(int _n) { n=_n;
	sz.resize(n, 1), par.resize(n), comp.resize(n, vector<int>(n, 0)); iota(all(par), 0);
	for (int i=0; i<n; i++) compo.insert(i);
}

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

bool same(int a, int b) { return get(a)==get(b); }

int merge(int a, int b) {
	a=get(a), b=get(b);
	if (a==b) return 0;
	if (a>b) swap(a, b);
	comp[a][b]++;
	if (comp[a][b]<sz[a]*sz[b]) return 0;
	if (sz[b]>sz[a]) swap(a, b);
	sz[a]+=sz[b];
	par[b]=a;
	for (auto u: compo) comp[min(a, u)][max(a, u)]+=comp[min(b, u)][max(b, u)];
	compo.erase(b);
	return 1;
}


int hasEdge(int u, int v) {
	return merge(u, v);
}

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