Submission #1062778

#	Time	Username	Problem	Language	Result	Execution time	Memory
1062778		Errichto	Game (IOI14_game)	C++14	100 / 100	504 ms	19280 KiB

game

#pragma once

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

int n;
vector<vector<bool>> removed;
vector<vector<bool>> isTree;
vector<vector<int>> edges;

void addTreeEdge(int a, int b) {
	isTree[a][b] = isTree[b][a] = true;
	edges[a].push_back(b);
	edges[b].push_back(a);
}
void eraseTreeEdge(int a, int b) {
	isTree[a][b] = isTree[b][a] = false;
	edges[a].erase(find(edges[a].begin(), edges[a].end(), b));
	edges[b].erase(find(edges[b].begin(), edges[b].end(), a));
}

void dfs(int a, vector<int>& collect, int parent = -1) {
	collect.push_back(a);
	for (int b : edges[a]) {
		if (b != parent) {
			dfs(b, collect, a);
		}
	}
}

void initialize(int _n) {
	n = _n;
	removed.resize(n, vector<bool>(n));
	isTree = removed;
	edges.resize(n);
	for (int i = 0; i < n - 1; i++) {
		addTreeEdge(i, i+1); // TODO, random
	}
}
int hasEdge(int a, int b) {
	removed[a][b] = removed[b][a] = true;
	if (!isTree[a][b]) {
		return 0;
	}
	eraseTreeEdge(a, b);
	vector<int> left, right;
	dfs(a, left);
	dfs(b, right);
	random_shuffle(left.begin(), left.end());
	random_shuffle(right.begin(), right.end());
	for (int x : left) {
		for (int y : right) {
			if (!removed[x][y]) {
				addTreeEdge(x, y);
				return 0;
			}
		}
	}
	return 1;
}

Compilation message (stderr)

game.cpp:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

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