Submission #162818

#	Time	Username	Problem	Language	Result	Execution time	Memory
162818		Minnakhmetov	Highway Tolls (IOI18_highway)	C++14	51 / 100	410 ms	262148 KiB

highway

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

using namespace std;

#define ll long long

struct E {
	int to, i;
};

const int N = 1e5 + 5;
vector<E> g[N], ord;
int anc[N];

void dfs(int node) {
	for (E e : g[node]) {
		if (e.to != anc[node]) {
			ord.push_back(e);
			anc[e.to] = node;
			dfs(e.to);
		}
	}
}

void find_pair(int n, vector<int> u, vector<int> v, int a, int b) {
	int m = u.size();

	for (int i = 0; i < m; i++) {
		g[u[i]].push_back({v[i], i});
		g[v[i]].push_back({u[i], i});
	}

	ll dist = ask(vector<int>(m, 0)) / a;

	dfs(0);

	// for (E e : ord) {
	// 	cout << e.to << " ";
	// }
	// cout << "\n";

	int s, t;

	int l = -1, r = ord.size() - 1;
	while (r - l > 1) {
		int p = (l + r) >> 1;
		vector<int> w(m);

		for (int i = 0; i <= p; i++)
			w[ord[i].i] = 1;

		if (ask(w) == dist * b)
			r = p;
		else
			l = p;
	}

	s = ord[r].to;

	l = -1, r = ord.size() - 1;
	while (r - l > 1) {
		int p = (l + r) >> 1;
		vector<int> w(m);

		for (int i = 0; i <= p; i++)
			w[ord[i].i] = 1;

		if (ask(w) > dist * a)
			r = p;
		else
			l = p;
	}

	int lca = anc[ord[r].to];

	// cout << lca << " " << s << "\n";

	int x = s;
	ll half = 0;
	while (x != lca) {
		half++;
		x = anc[x];
	}

	if (half == dist) {
		t = lca;
	}
	else {
		l = -1, r = ord.size() - 1;
		while (r - l > 1) {
			int p = (l + r) >> 1;
			vector<int> w(m);

			for (int i = 0; i <= p; i++)
				w[ord[i].i] = 1;

			if (ask(w) >= dist * a + (dist - half) * (b - a))
				r = p;
			else
				l = p;
		}

		t = ord[r].to;
	}

	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