Submission #1041458

#	Time	Username	Problem	Language	Result	Execution time	Memory
1041458		yanb	Highway Tolls (IOI18_highway)	C++14	0 / 100	5 ms	856 KiB

highway

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

void find_pair(signed n, vector<signed> U, vector<signed> V, signed A, signed B) {
	vector<int> p(n, -1), e(n, -1);
	vector<bool> leaf(n, 1);
	for (int i = 0; i < n - 1; i++) {
		int u = min(U[i], V[i]), v = max(U[i], V[i]);
		leaf[u] = 0;
		p[v] = u;
		e[v] = i;
	}

	int k = 0;
	vector<int> leaves;
	for (int i = 0; i < n; i++) {
		if (leaf[i]) {
			leaves.push_back(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) == zero) l = md;
		else r = md;
	}

	int v = leaves[l];
	int vdist = 0;
	while (p[v] != -1) {
		v = p[v];
		vdist++;
	}
	v = leaves[l];
	for (int i = 0; i < vdist - dist; i++) {
		v = p[v];
	}

	answer(0, v);
}

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