Submission #656502

#	Time	Username	Problem	Language	Result	Execution time	Memory
656502		MateGiorbelidze	Game (IOI14_game)	C++14	100 / 100	416 ms	26884 KiB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first
#define sc second
#define pb push_back
#define in insert

int N;
ll ans[1501][1501];
ll p[1501];

void make_set(ll v) {
	
	p[v] = v;
	
	for (int i = 0; i < N; i++)
		ans[v][i] = 1;
		
}

ll find_par(ll v) {
	
	if (p[v] == v) return v;
	else return p[v] = find_par(p[v]);
	
}

ll union_sets (ll a, ll b) {
	
	a = find_par(a); b = find_par(b);
	
	if (a == b) return 0;
	
	if (ans[a][b] == 1) {
		
		ans[a][b]--;
		ans[b][a]--;
		
		for (int i = 0; i < N; i++){
			
			ans[a][i] += ans[b][i];
			ans[i][a] += ans[i][b];
			ans[b][i] = 0;
			ans[i][b] = 0;
		}
		
		p[b] = a;
		
		return 1;
	}
	
	ans[a][b]--;
	ans[b][a]--;
	
	return 0;
}

void initialize(int n) {
	N = n;
	
	for (int i = 0; i < n; i++)
		make_set(i);
}

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

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