Submission #414453

#	Time	Username	Problem	Language	Result	Execution time	Memory
414453		Temmie	Highway Tolls (IOI18_highway)	C++17	0 / 100	16 ms	996 KiB

highway

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

typedef long long ll;

//ll ask(std::vector <int> v) {
	//return 0;
//}

//void answer(int s, int t) {
	//std::cerr << "answered: (" << s << ", " << t << ")" << std::endl;
//}

void find_pair(int n, std::vector <int> U, std::vector <int> V, int A, int B) {
	assert((int)U.size() == n - 1); // only tree subtasks
	// ( index of nieghbor, index of edge in U/V )
	std::vector <std::vector <std::pair <int, int>>> g(n);
	for (int i = 0; i < n - 1; i++) {
		g[U[i]].push_back({ V[i], i });
		g[V[i]].push_back({ U[i], i });
	}
	std::pair <int, int> ans = { -1, -1 };
	int root1 = -1, root2 = -1;
	ll whole = ask({ });
	{
		int l = 0, r = n - 1;
		int best = n;
		while (l <= r) {
			int mid = (l + r) >> 1;
			std::vector <int> v(n - 1, 0);
			for (int i = l; i <= mid; i++ ) {
				v[i] = 1;
			}
			ll now = ask(v);
			if (now > whole) {
				// contains at least one edge of path
				best = mid;
				r = mid - 1;
			} else {
				// contains no edges of path
				l = mid + 1;
			}
		}
		assert(best != n);
		root1 = U[best];
		root2 = V[best];
	}
	{
		int root = root1;
		int otherroot = root2;
		std::vector <int> wholeTree(n - 1, 0);
		std::queue <std::pair <int, int>> q; // ( node, par )
		q.push({ root, otherroot });
		std::vector <int> dep(n, -1);
		dep[root] = 0;
		std::vector <int> edgeUp(n, -1);
		while (q.size()) {
			auto p = q.front(); q.pop();
			for (auto x : g[p.first]) if (x.first != p.second) {
				wholeTree[x.second] = 1;
				q.push({ x.first, p.first });
				dep[x.first] = dep[p.first] + 1;
				edgeUp[x.first] = x.second;
			}
		}
		ll query = ask(wholeTree);
		int depthWanted = (query - whole) / ll(B);
		assert(depthWanted >= 0);
		if (depthWanted == 0) {
			// root is also ans
			ans.first = root;
		}
		// ( node, edge up )
		std::vector <std::pair <int, int>> possible;
		for (int i = 0; i < n; i++) {
			if (dep[i] == depthWanted) {
				assert(edgeUp[i] != -1);
				possible.emplace_back(i, edgeUp[i]);
			}
		}
		int l = 0, r = (int)possible.size() - 1;
		int best = possible.size();
		while (l <= r) {
			int mid = (l + r) >> 1;
			std::vector <int> v(n - 1, 0);
			for (int i = l; i <= mid; i++) {
				v[possible[i].second] = 1;
			}
			ll now = ask(v);
			if (now == whole) {
				// inside
				best = mid;
				r = mid - 1;
			} else {
				l = mid + 1;
			}
		}
		assert(best != (int)possible.size());
		ans.first = possible[best].first;
	}
	{
		int root = root1;
		int otherroot = root2;
		std::swap(root, otherroot);
		std::vector <int> wholeTree(n - 1, 0);
		std::queue <std::pair <int, int>> q; // ( node, par )
		q.push({ root, otherroot });
		std::vector <int> dep(n, -1);
		dep[root] = 0;
		std::vector <int> edgeUp(n, -1);
		while (q.size()) {
			auto p = q.front(); q.pop();
			for (auto x : g[p.first]) if (x.first != p.second) {
				wholeTree[x.second] = 1;
				q.push({ x.first, p.first });
				dep[x.first] = dep[p.first] + 1;
				edgeUp[x.first] = x.second;
			}
		}
		ll query = ask(wholeTree);
		int depthWanted = (query - whole) / ll(B);
		assert(depthWanted >= 0);
		if (depthWanted == 0) {
			// root is also ans
			ans.second = root;
		}
		// ( node, edge up )
		std::vector <std::pair <int, int>> possible;
		for (int i = 0; i < n; i++) {
			if (dep[i] == depthWanted) {
				assert(edgeUp[i] != -1);
				possible.emplace_back(i, edgeUp[i]);
			}
		}
		int l = 0, r = (int)possible.size() - 1;
		int best = possible.size();
		while (l <= r) {
			int mid = (l + r) >> 1;
			std::vector <int> v(n - 1, 0);
			for (int i = l; i <= mid; i++) {
				v[possible[i].second] = 1;
			}
			ll now = ask(v);
			if (now == whole) {
				// inside
				best = mid;
				r = mid - 1;
			} else {
				l = mid + 1;
			}
		}
		assert(best != (int)possible.size());
		ans.second = possible[best].first;
	}
	answer(ans.first, ans.second);
}

//int main() {
	
//}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 6
• Subtask 4: 0 / 33
• Subtask 5: 0 / 18
• Subtask 6: 0 / 31