Submission #594819

#	Time	Username	Problem	Language	Result	Execution time	Memory
594819		Temmie	Highway Tolls (IOI18_highway)	C++17	51 / 100	214 ms	9572 KiB

highway

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

int n, m;
std::vector <std::vector <int>> g;

long long dist;

void find_pair(int _n, std::vector <int> _u, std::vector <int> _v, int a, int b) {
	n = _n;
	m = _u.size();
	g.resize(n);
	for (int i = 0; i < m; i++) {
		g[_u[i]].push_back(i);
		g[_v[i]].push_back(i);
	}
	dist = ask(std::vector <int> (m, 0)) / a;
	int root[2] = { -1, -1 };
	int sec = -1;
	{
		int l = 0, r = m - 1, best = m - 1;
		while (l <= r) {
			int mid = (l + r) >> 1;
			std::vector <int> cur(m, 0);
			for (int i = l; i <= mid; i++) {
				cur[i] = 1;
			}
			long long val = ask(cur);
			if (val != dist * a) {
				best = mid;
				r = mid - 1;
			} else {
				l = mid + 1;
			}
		}
		root[0] = _u[best];
		root[1] = _v[best];
		sec = best;
		
		//std::vector <int> cur(m, 1);
		//int left = m;
		//while (left > 1) {
			//auto cop = cur;
			//int mid = left >> 1;
			//for (int i = 0; i < m && left > mid; i++) {
				//if (cur[i]) {
					//left--;
					//cur[i] = 0;
				//}
			//}
			//long long val = ask(cur);
			//if (val > dist * a) {
				//left = 0;
				//for (int x : cur) {
					//left += x;
				//}
			//} else {
				//left = 0;
				//for (int i = 0; i < m; i++) {
					//if (cur[i] && cop[i]) {
						//cop[i] = 0;
					//}
					//left += cop[i];
				//}
				//cur = cop;
			//}
		//}
		//assert(left == 1);
		//for (int i = 0; i < m; i++) {
			//if (cur[i]) {
				//sec = i;
				//root[0] = _u[i];
				//root[1] = _v[i];
				//break;
			//}
		//}
	}
	assert(root[0] != -1 && root[1] != -1);
	assert(sec != -1);
	std::vector <int> nod[2];
	std::vector <int> par(n, -1);
	{
		std::queue <std::pair <int, std::pair <int, int>>> q;
		q.push({ root[0], { sec, root[0] } });
		q.push({ root[1], { sec, root[1] } });
		std::vector <bool> vis(n, false);
		while (q.size()) {
			int rt = q.front().first;
			int pa = q.front().second.first;
			int v = q.front().second.second;
			q.pop();
			if (vis[v]) {
				continue;
			}
			vis[v] = true;
			par[v] = pa;
			nod[rt == root[0] ? 0 : 1].push_back(v);
			for (int x : g[v]) {
				int to = v ^ _u[x] ^ _v[x];
				q.push({ rt, { x, to } });
			}
		}
	}
	int ans[2];
	for (int i = 0; i <= 1; i++) {
		int l = 0, r = (int) nod[i].size() - 1, best = nod[i][0];
		while (l < r) {
			int mid = (l + r) >> 1;
			std::vector <int> cur(m, 1);
			for (int x : nod[i ^ 1]) {
				cur[par[x]] = 0;
			}
			for (int j = 0; j <= mid; j++) {
				cur[par[nod[i][j]]] = 0;
			}
			long long val = ask(cur);
			if (val > dist * a) {
				best = nod[i][mid + 1];
				l = mid + 1;
			} else {
				r = mid;
			}
		}
		ans[i] = best;
	}
	answer(ans[0], ans[1]);
}

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