Submission #769060

#	Time	Username	Problem	Language	Result	Execution time	Memory
769060		SanguineChameleon	Highway Tolls (IOI18_highway)	C++17	51 / 100	184 ms	262144 KiB

highway

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

const int maxN = 9e4 + 20;
vector<pair<int, int>> adj[maxN];
int sz[maxN];
int depth[maxN];
int par_id[maxN];
vector<pair<int, int>> group[maxN];
bool flag[maxN];
int N, M, A, B;

void dfs1(int u, int p) {
	for (auto e: adj[u]) {
		int v = e.first;
		int id = e.second;
		if (v != p) {
			depth[v] = depth[u] + 1;
			par_id[v] = id;
			dfs1(v, u);
		}
	}
}

int find_depth(int root, int d, long long mi) {
	if (d == 0) {
		return root;
	}
	depth[root] = 0;
	dfs1(root, -1);
	vector<int> query(M, 0);
	vector<pair<int, int>> cand;
	for (int i = 0; i < N; i++) {
		if (depth[i] == d) {
			cand.emplace_back(i, par_id[i]);
		}
	}
	while ((int)cand.size() > 1) {
		int sz = cand.size();
		vector<pair<int, int>> left(cand.begin(), cand.begin() + sz / 2);
		vector<pair<int, int>> right(cand.begin() + sz / 2, cand.end());
		for (auto p: left) {
			query[p.second] = 1;
		}
		long long res = ask(query);
		for (auto p: left) {
			query[p.second] = 0;
		}
		if (res == mi) {
			cand = right;
		}
		else {
			cand = left;
		}
	}
	return cand[0].first;
}

void dfs2(int u, int p) {
	sz[u] = 1;
	for (auto e: adj[u]) {
		int v = e.first;
		if (v != p && !flag[v]) {
			dfs2(v, u);
			sz[u] += sz[v];
		}
	}
}

int cen(int r, int u, int p) {
	for (auto e: adj[u]) {
		int v = e.first;
		if (v != p && !flag[v] && sz[v] * 2 > sz[r]) {
			return cen(r, v, u);
		}
	}
	return u;
}

void build(int u, int d) {
	dfs2(u, -1);
	u = cen(u, u, -1);
	flag[u] = true;
	for (auto e: adj[u]) {
		int v = e.first;
		int id = e.second;
		if (!flag[v]) {
			group[d].emplace_back(u, id);
			build(v, d + 1);
		}
	}
}

vector<int> query;

void dfs3(int u, int p) {
	for (auto e: adj[u]) {
		int v = e.first;
		int id = e.second;
		if (v != p) {
			query[id] = 1;
			dfs3(v, u);
		}
	}
}

void find_pair(int _N, vector<int> U, vector<int> V, int _A, int _B) {
	N = _N;
	M = U.size();
	A = _A;
	B = _B;
	for (int i = 0; i < M; i++) {
		adj[U[i]].emplace_back(V[i], i);
		adj[V[i]].emplace_back(U[i], i);
	}
	int dist = ask(vector<int>(M, 0)) / A;
	build(0, 0);
	int root = -1;
	int sub = -1;
	query.resize(M);
	for (int d = 0; ; d++) {
		for (auto p: group[d]) {
			query[p.second] = 1;
		}
		long long res = ask(query);
		for (auto p: group[d]) {
			query[p.second] = 0;
		}
		if (res != 1LL * A * dist) {
			vector<pair<int, int>> cand = group[d];
			while ((int)cand.size() > 1) {
				int sz = cand.size();
				vector<pair<int, int>> left(cand.begin(), cand.begin() + sz / 2);
				vector<pair<int, int>> right(cand.begin() + sz / 2, cand.end());
				for (auto p: left) {
					query[p.second] = 1;
				}
				long long res = ask(query);
				for (auto p: left) {
					query[p.second] = 0;
				}
				if (res == 1LL * A * dist) {
					cand = right;
				}
				else {
					cand = left;
				}
			}
			root = cand[0].first;
			int id = cand[0].second;
			query[id] = 1;
			sub = (U[id] == root ? V[id] : U[id]);
			break;
		}
	}
	dfs3(sub, root);
	int d = (ask(query) - 1LL * A * dist) / (B - A);
	d = max(d, dist - d);
	int S = find_depth(root, d, 1LL * A * dist);
	int T = find_depth(S, dist, 1LL * A * dist);
	answer(S, T);
}

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