Submission #779163

#	Time	Username	Problem	Language	Result	Execution time	Memory
779163		NothingXD	Game (IOI14_game)	C++17	100 / 100	380 ms	28092 KiB

game

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

using namespace std;

typedef long long ll;
typedef double ld;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef complex<double> point;

void debug_out(){cerr << endl;}

template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T){
	cerr << H << ' ';
	debug_out(T...);
}

#define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)

const int maxn = 2e3 + 10;

int n, par[maxn], cnt[maxn][maxn];

int getpar(int v){
	return (par[v] == -1? v: par[v] = getpar(par[v]));
}

void merge(int u, int v){
	if ((v = getpar(v)) == (u = getpar(u))) return;
	for (int i = 0; i < n; i++){
		cnt[u][i] += cnt[v][i];
		cnt[i][u] += cnt[i][v];
	}
	par[v] = u;
}

void initialize(int _n) {
	n = _n;
	memset(par, -1, sizeof par);
	for (int i = 0; i < n; i++){
		for (int j = 0; j < n; j++) cnt[i][j] = 1;
	}
}

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

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