Submission #112268

#	Time	Username	Problem	Language	Result	Execution time	Memory
112268		JustInCase	Meetings (JOI19_meetings)	C++17	100 / 100	1121 ms	191608 KiB

meetings

#include <bits/stdc++.h>
#ifndef skeletaZaPrezident
	#include "meetings.h"
#endif

#define query Query
#define bridge Bridge
#define solve Solve

#define int32_t int
#define int64_t long long

const int32_t MAX_N = 2000;

#ifdef skeletaZaPrezident
int32_t query(int32_t u, int32_t v, int32_t w) {
	std::cout << u << " " << v << " " << w << '\n' << std::flush;

	int32_t res;
	std::cin >> res;

	return res;
}

void bridge(int32_t u, int32_t v) {
	std::cout << "edge: " << u << " " << v << '\n' << std::flush;
}
#endif

#ifndef sekeletaZaPrezident
int32_t query(int32_t u, int32_t v, int32_t w);
void bridge(int32_t u, int32_t v);
#endif

std::map< int32_t, int32_t > asked[MAX_N + 5][MAX_N + 5];

int32_t ask_query(int32_t x, int32_t y, int32_t z) {
	int32_t a[] = { x, y, z };
	std::sort(a, a + 3);

	if(asked[a[0]][a[1]].count(a[2]) == 0) {
		asked[a[0]][a[1]][a[2]] = query(a[0], a[1], a[2]);
	}

	return asked[a[0]][a[1]][a[2]];
}

struct Vertex {
	bool vis;
	int32_t subtreeSize;
	std::vector< int32_t > adjList;

	Vertex() : vis(false), subtreeSize(1) {}
};

bool isInserted[MAX_N + 5];
Vertex t[MAX_N + 5];

bool sort_by_subtree_size(int32_t u, int32_t v) {
	return t[u].subtreeSize > t[v].subtreeSize;
}

void init(int32_t n) {
	for(int32_t i = 0; i < n; i++) {
		t[i].vis = false;
	}
}

void compute_subtree_sizes(int32_t v, int32_t par) {
	t[v].subtreeSize = 1;

	for(auto &x : t[v].adjList) {
		if(x == par || t[x].vis) {
			continue;
		}

		compute_subtree_sizes(x, v);
		t[v].subtreeSize += t[x].subtreeSize;
	}
}

int32_t find_centroid(int32_t v, int32_t par, int32_t target) {
	int32_t maxSubtree = -1, ind = -1;
	for(auto &x : t[v].adjList) {
		if(x == par || t[x].vis) {
			if(t[x].vis) {
				t[x].subtreeSize = 0;
			}

			continue;
		}

		if(t[x].subtreeSize > maxSubtree) {
			maxSubtree = t[x].subtreeSize;
			ind = x;
		}
	}

	if(ind != -1 && maxSubtree > target / 2) {
		return find_centroid(ind, v, target);
	}

	return v;
}

void solve_vertex(int32_t root, int32_t v) {
	compute_subtree_sizes(root, -1);
	int32_t centroid = find_centroid(root, -1, t[root].subtreeSize);
	compute_subtree_sizes(centroid, -1);
	int32_t aux;
	
	std::sort(t[centroid].adjList.begin(), t[centroid].adjList.end(), sort_by_subtree_size);
	for(int32_t i = 0; i < (int32_t) t[centroid].adjList.size(); i++) {
		if(i == (int32_t) t[centroid].adjList.size() - 1) {
			aux = ask_query(centroid, t[centroid].adjList[i], v);

			if(aux == v) {
				t[t[centroid].adjList[i]].adjList.push_back(v);
				t[v].adjList.push_back(t[centroid].adjList[i]);

				t[t[centroid].adjList[i]].adjList.erase(std::find(t[t[centroid].adjList[i]].adjList.begin(), t[t[centroid].adjList[i]].adjList.end(), centroid));
				t[centroid].adjList.erase(t[centroid].adjList.begin() + i);

				t[centroid].adjList.push_back(v);
				t[v].adjList.push_back(centroid);
				return;
			}

			if(aux == t[centroid].adjList[i]) {
				t[centroid].vis = true;
				solve_vertex(t[centroid].adjList[i], v);
				return;
			}

			if(aux != centroid) {
				solve_vertex(aux, v);
				
				t[t[centroid].adjList[i]].adjList.push_back(aux);
				t[aux].adjList.push_back(t[centroid].adjList[i]);

				t[t[centroid].adjList[i]].adjList.erase(std::find(t[t[centroid].adjList[i]].adjList.begin(), t[t[centroid].adjList[i]].adjList.end(), centroid));
				t[centroid].adjList.erase(t[centroid].adjList.begin() + i);

				t[centroid].adjList.push_back(aux);
				t[aux].adjList.push_back(centroid);
		
				isInserted[aux] = true;

				return;
			}

			break;
		}

		aux = ask_query(t[centroid].adjList[i], t[centroid].adjList[i + 1], v);

		// v is on the path from t[centroid].adjList[i] to t[centroid].adjList[i + 1]
		if(aux == v) {
			aux = ask_query(t[centroid].adjList[i], centroid, v);

			if(aux == centroid) {
				t[t[centroid].adjList[i + 1]].adjList.push_back(v);
				t[v].adjList.push_back(t[centroid].adjList[i + 1]);

				t[t[centroid].adjList[i + 1]].adjList.erase(std::find(t[t[centroid].adjList[i + 1]].adjList.begin(), t[t[centroid].adjList[i + 1]].adjList.end(), centroid));
				t[centroid].adjList.erase(t[centroid].adjList.begin() + i + 1);
				
				t[centroid].adjList.push_back(v);
				t[v].adjList.push_back(centroid);
			
				return;
			}
		
			t[t[centroid].adjList[i]].adjList.push_back(v);
			t[v].adjList.push_back(t[centroid].adjList[i]);

			t[t[centroid].adjList[i]].adjList.erase(std::find(t[t[centroid].adjList[i]].adjList.begin(), t[t[centroid].adjList[i]].adjList.end(), centroid));
			t[centroid].adjList.erase(t[centroid].adjList.begin() + i);
			
			t[centroid].adjList.push_back(v);
			t[v].adjList.push_back(centroid);

			return;
		}

		if(aux == t[centroid].adjList[i]) {
			t[centroid].vis = true;
			solve_vertex(t[centroid].adjList[i], v);
			return;
		}

		if(aux == t[centroid].adjList[i + 1]) {
			t[centroid].vis = true;
			solve_vertex(t[centroid].adjList[i + 1], v);
			return;
		}

		if(aux != centroid) {
			solve_vertex(aux, v);
			
			int32_t aux2 = ask_query(t[centroid].adjList[i], aux, centroid);
			if(aux2 == centroid) {
				t[t[centroid].adjList[i + 1]].adjList.push_back(aux);
				t[aux].adjList.push_back(t[centroid].adjList[i + 1]);

				t[t[centroid].adjList[i + 1]].adjList.erase(std::find(t[t[centroid].adjList[i + 1]].adjList.begin(), t[t[centroid].adjList[i + 1]].adjList.end(), centroid));
				t[centroid].adjList.erase(t[centroid].adjList.begin() + i + 1);

				t[centroid].adjList.push_back(aux);
				t[aux].adjList.push_back(centroid);
			}
			else {
				t[t[centroid].adjList[i]].adjList.push_back(aux);
				t[aux].adjList.push_back(t[centroid].adjList[i]);

				t[t[centroid].adjList[i]].adjList.erase(std::find(t[t[centroid].adjList[i]].adjList.begin(), t[t[centroid].adjList[i]].adjList.end(), centroid));
				t[centroid].adjList.erase(t[centroid].adjList.begin() + i);

				t[centroid].adjList.push_back(aux);
				t[aux].adjList.push_back(centroid);
			}

			isInserted[aux] = true;
			
			return;
		}
	}

	t[centroid].adjList.push_back(v);
	t[v].adjList.push_back(centroid);
}

void solve(int32_t n) {
	t[0].adjList.push_back(1);
	t[1].adjList.push_back(0);
	
	// solve for each node
	for(int32_t i = 2; i < n; i++) {
		if(isInserted[i]) {
			continue;
		}

		init(n);
		solve_vertex(0, i);	
	}

	for(int32_t i = 0; i < n; i++) {
		for(auto &x : t[i].adjList) {
			if(x > i) {
				bridge(i, x);
			}
		}
	}
}

• Subtask 1: 7 / 7
• Subtask 2: 10 / 10
• Subtask 3: 12 / 12
• Subtask 4: 71 / 71