Submission #1277078

#	Time	Username	Problem	Language	Result	Execution time	Memory
1277078		crispxx	Game (IOI14_game)	C++20	100 / 100	200 ms	16024 KiB

game

#include "game.h"

#include <bits/stdc++.h>
using namespace std;

// #define int long long
#define all(x) x.begin(), x.end()
#define pb push_back
#define ar array
#define nl '\n'

const int N = 1500;

int s[N][N], d[N];

vector<int> lst[N];

int n;

void initialize(int m) {
	n = m;
	for(int i = 0; i < n; i++) {
		d[i] = i;
		lst[i].clear();
		lst[i].pb(i);
		for(int j = 0; j < n; j++) {
			if(i != j) s[i][j] = 1;
		}
	}
}

bool merge(int u, int v) {
	u = d[u], v = d[v];
	if(u == v) return false;
	if(lst[u].size() < lst[v].size()) swap(u, v);
	if(s[u][v] > 1) {
		s[u][v]--;
		s[v][u]--;
		return false;
	} else {
		for(auto &x : lst[v]) {
			d[x] = u;
			lst[u].pb(x);
		}
		for(int x = 0; x < n; x++) {
			if(x == d[x] && x != u && x != v) {
				int t = s[u][x] + s[v][x];
				s[u][x] = s[x][u] = t;
			}
		}
		return true;
	}
}

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

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