Submission #769050

#	Time	Username	Problem	Language	Result	Execution time	Memory
769050		SanguineChameleon	Highway Tolls (IOI18_highway)	C++17	5 / 100	208 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 depth[maxN];
int par_id[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) {
	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;
		}
		int res = ask(query);
		for (auto p: left) {
			query[p.second] = 0;
		}
		if (res == 1LL * A * d) {
			cand = right;
		}
		else {
			cand = left;
		}
	}
	return cand[0].first;
}

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;
	int S = find_depth(0, 0);
	int T = find_depth(S, dist);
	answer(S, T);
}

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