Submission #105073

#	Time	Username	Problem	Language	Result	Execution time	Memory
105073		groeneprof	Game (IOI14_game)	C++14	100 / 100	683 ms	16172 KiB

game

#include <bits/stdc++.h>
#include "game.h"
using namespace std;
vector<int> uf;
vector<vector<int> > graph;
int n;
int root(int a){
	if(uf[a]==a) return a;
	return uf[a] = root(uf[a]);
}

void merge(int a, int b){
	a = root(a); b = root(b);
	if(rand()%2){
		swap(a, b);
	}
	uf[b] = a;
	for(int i = 0; i<n; i++){
		graph[a][i] += graph[b][i];
		graph[i][a] += graph[i][b];
	}
}

void initialize(int N) {
	n=N;
	uf.resize(n);
	for(int i = 0; i<n; i++) uf[i] = i;
	graph.resize(n, vector<int> (n, 1));
}

int hasEdge(int u, int v) {
	u = root(u);
	v = root(v);
    if(graph[u][v]==1){
    	merge(u,v);
    	return 1;
    }
    else{
    	graph[u][v]--;
    	graph[v][u]--;
    	return 0;
    }
    return 2;
}

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