Submission #835141

#	Time	Username	Problem	Language	Result	Execution time	Memory
835141		gustason	Game (IOI14_game)	C++14	0 / 100	1 ms	212 KiB

game

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

constexpr int nax = 81;
int N;

struct Dsu {
	int par[nax];
	int sz[nax];
	
	Dsu(int n=nax) {
		for(int i = 0; i < n; i++) {
			par[i] = i;
			sz[i] = 1;
		}
	}
	
	int find(int v) {
		if (par[v] == v) {
			return v;
		}
		return par[v] = find(par[v]);
	}
	
	bool unite(int a, int b) {
		a = find(a), b = find(b);
		
		if (a == b) {
			return false;
		}
		if (sz[b] > sz[a]) {
			swap(a, b);
		}
		
		par[b] = a;
		sz[a] += sz[b];
		return true;
	}
	
	bool form_full() {
		return sz[find(0)] == N;
	}
};

bool form_full(Dsu a, Dsu& b) {
	for(int i = 0; i < N; i++) {
		for(int j = i+1; j < N; j++) {
			if (b.find(i) == b.find(j)) {
				a.unite(i, j);
			}
		}
	}
	
	return a.form_full();
}

Dsu curr;
vector<pair<int, int>> edges;

void initialize(int n) {
	N = n;
	// curr + all Yes -> form full
	// curr + all No -> not form full
	
	for(int i = 0; i < n; i++) {
		for(int j = i+1; j < n; j++) {
			edges.emplace_back(i, j);
		}
	}
}

int hasEdge(int u, int v) {
	if (u > v) {
		swap(u, v);
	}
	
	edges.erase(find(edges.begin(), edges.end(), pair<int, int>(u, v)));
	
	Dsu curr_add = curr;
	curr_add.unite(u, v);
	
	if (curr_add.form_full()) {
		return 0;
	}
	
	Dsu curr_all = curr_add;
	for(auto& i : edges) {
		curr_all.unite(i.first, i.second);
	}
	
	if (!curr_all.form_full()) {
		return 0;
	}
	
	curr = curr_add;
    return 1;
}

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