Submission #558528

#	Time	Username	Problem	Language	Result	Execution time	Memory
558528		Trunkty	Game (IOI14_game)	C++14	100 / 100	456 ms	20252 KiB

game

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include "game.h"
using namespace std;
typedef long long ll;

#define DEBUG
#ifdef DEBUG
  #define debug(x) cout << #x << ": " << x << endl
#else
  #define debug(x)
#endif

int root[1505];
int cnt[1505][1505];
set<int> s;

int findroot(int x){
	if(root[x]!=x){
		root[x] = findroot(root[x]);
	}
	return root[x];
}

void domerge(int x, int y){
	s.erase(y);
	for(int i:s){
		if(i==x){
			continue;
		}
		cnt[x][i] += cnt[y][i];
		cnt[i][x] += cnt[y][i];
		cnt[y][i] = 0;
		cnt[i][y] = 0;
	}
	root[y] = x;
}

void initialize(int n){
	for(int i=0;i<n;i++){
		root[i] = i;
		for(int j=0;j<n;j++){
			if(i!=j){
				cnt[i][j] = 1;
			}
		}
		s.insert(i);
	}
}

int hasEdge(int u, int v){
	u = findroot(u);
	v = findroot(v);
	cnt[u][v]--;
	cnt[v][u]--;
	if(cnt[u][v]){
		return 0;
	}
	domerge(u,v);
	return 1;
}

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