Submission #1041503

#	Time	Username	Problem	Language	Result	Execution time	Memory
1041503		yanb	Highway Tolls (IOI18_highway)	C++14	18 / 100	185 ms	262144 KiB

highway

#include <bits/stdc++.h>
#include "highway.h"
    
using namespace std;
    
#define int long long
#define pii pair<long long, long long>

void dfs(int v, vector<vector<pii>> &g, vector<int> &p, vector<int> &e, vector<bool> &leaf) {
	for (auto [u, eu] : g[v]) {
		if (u != p[v]) {
			p[u] = v;
			e[u] = eu;
			leaf[v] = 0;
			dfs(u, g, p, e, leaf);
		}
	}
}

int find_one(int n, vector<signed> U, vector<signed> V, int A, int B, int S) {
	vector<int> p(n, -1), e(n, -1);
	vector<bool> leaf(n, 1);
	vector<vector<pii>> 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});
	}
	dfs(S, g, p, e, leaf);

	int k = 0;
	vector<int> leaves;
	for (int i = 0; i < n; i++) {
		if (leaf[i]) {
			leaves.push_back(i);
			//cout << i << " ";
			k++;
		}
	}
	//cout << "\n";

	vector<signed> w(n - 1);
	int zero = ask(w);
	int dist = zero / A;
	
	int l = -1, r = k;
	while (r - l > 1) {
		int md = (l + r) / 2;
		vector<signed> w(n - 1);
		for (int i = 0; i < md; i++) {
			int v = leaves[i];
			while (p[v] != -1 && !w[e[v]]) {
				w[e[v]] = 1;
				v = p[v];
			}
		}
		if (ask(w) != dist * B) l = md;
		else r = md;
	}

	//cout << r << "\n";

	int v = leaves[l], vdist = 0;
	while (p[v] != -1) {
		v = p[v];
		vdist++;
	}
	int ll = 0, rr = vdist + 1;
	while (rr - ll > 1) {
		int md = (ll + rr) / 2;
		vector<signed> w(n - 1);
		int v = leaves[l];
		for (int i = 0; i < md; i++) {
			w[e[v]] = 1;
			v = p[v];
		}
		if (ask(w) == zero) ll = md;
		else rr = md;
	}

	v = leaves[l];
	for (int i = 0; i < ll; i++) {
		v = p[v];
	}

	return v;
}

void find_pair(signed n, vector<signed> U, vector<signed> V, signed A, signed B) {
	int u = find_one(n, U, V, A, B, 0);
	int v = find_one(n, U, V, A, B, u);

	answer(u, v);
}

Compilation message (stderr)

highway.cpp: In function 'void dfs(long long int, std::vector<std::vector<std::pair<long long int, long long int> > >&, std::vector<long long int>&, std::vector<long long int>&, std::vector<bool>&)':
highway.cpp:10:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   10 |  for (auto [u, eu] : g[v]) {
      |            ^

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