Submission #1199213

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199213		alind	Highway Tolls (IOI18_highway)	C++20	11 / 100	78 ms	21364 KiB

highway

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

using namespace std;

typedef long long ll;

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
	int M = U.size();
	assert (M == N - 1);
	vector<int> pa(N, -1), ei(N, -1), dep(N, 0);
	vector<vector<pair<int, int>>> gr(N);
	for (int i = 0; i < N-1; i++) {
		gr[U[i]].push_back({V[i], i});
		gr[V[i]].push_back({U[i], i});
	}
	auto build = [&](auto &&self, int v, int p) -> void {
		for (auto [u, i] : gr[v]) if (u != p) {
			pa[u] = v;
			ei[u] = i;
			dep[u] = dep[v] + 1;
			self(self, u, v);
		}
	};
	build(build, 0, -1);
	vector<int> w(M, 0);
	ll bfs = ask(w);
	srand(260504);
	set<int> vis, cur; for (int i = 0; i < N; i++) cur.insert(i);
	auto f = [&](auto &&self, int v) -> void {
		if (v) w[ei[v]] = 1;
		vis.insert(v);
		for (auto [u, i] : gr[v]) if (u != pa[v] && cur.count(u)) self(self, u);
	};
	set<int> z, oth;
	while (1) {
		vis.clear();
		w.assign(M, 0);
		int ch = rand() % N;
		while (!cur.count(ch)) ch = rand() % N;
		f(f, ch);
		ll d = ask(w);
		if (d == bfs)
			for (auto x : vis) cur.erase(x);
		else if (d * A == bfs * B) {
			swap(vis, cur);
			if (ch) cur.insert(pa[ch]);
		}
		else {
			for (auto x : vis) cur.erase(x);
			if (ch) vis.erase(pa[ch]);
			int y = (d - bfs) / (B - A);
			assert (1ll * y * (B - A) == d - bfs);
			for (auto x : vis) if (dep[x] - dep[pa[ch]] == y) z.insert(x);
			swap(oth, cur);
			break;
		}
	}
	while (z.size() > 1) {
		w.assign(M, 0);
		set<int> ch;
		for (auto x : z) if (rand() % 2) {
			ch.insert(x);
			w[ei[x]] = 1;
		}
		ll d = ask(w);
		if (d == bfs) {for (auto x : ch) z.erase(x);}
		else swap(z, ch);
	}
	assert (z.size() == 1);
	int s = *z.begin();
	z.clear();
	auto re = [&](auto &&self, int v, int p, int d) -> void {
		if (oth.count(v) && 1ll * d * A == bfs) z.insert(v);
		for (auto [u, i] : gr[v]) if (u != p) {
			ei[u] = i;
			self(self, u, v, d + 1);
		}
	};
	re(re, s, -1, 0);
	while (z.size() > 1) {
		w.assign(M, 0);
		set<int> ch;
		for (auto x : z) if (rand() % 2) {
			ch.insert(x);
			w[ei[x]] = 1;
		}
		ll d = ask(w);
		if (d == bfs) {for (auto x : ch) z.erase(x);}
		else swap(z, ch);
	}
	assert (z.size() == 1);
	int t = *z.begin();
	answer(s, t);
}

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