Submission #303282

#	Time	Username	Problem	Language	Result	Execution time	Memory
303282		sofapuden	Game (IOI14_game)	C++14	100 / 100	598 ms	25464 KiB

game

#include "game.h"
#include <bits/stdc++.h>

using namespace std;

int _n;
vector<vector<int>> e;
vector<int> ufa;

int uf(int ind){
	if(ufa[ind] == ind)return ind;
	ufa[ind] = uf(ufa[ind]);
	return ufa[ind];
}

void initialize(int n) {
	_n = n;
	ufa.resize(n);
	iota(ufa.begin(), ufa.end(), 0);
	e.resize(n, vector<int> (n,1));
}

int hasEdge(int u, int v) {
	u = uf(u); v = uf(v);
	if(u == v)return 1;
	if(e[u][v] == 1){
		ufa[u] = ufa[v];
		for(int i = 0; i < _n; ++i){
			e[v][i]+=e[u][i];
			e[i][v]+=e[i][u];
		}
		return 1;
	}
	e[u][v]--;
	e[v][u]--;
	return 0;	
}

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