Submission #412242

#	Time	Username	Problem	Language	Result	Execution time	Memory
412242		Mlxa	Highway Tolls (IOI18_highway)	C++14	5 / 100	268 ms	262148 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) x.begin(), x.end()
#define mp make_pair
#define mt make_tuple
#define x first
#define y second

namespace my {
const int N = 1e6 + 10;
struct edge {
	int u, i;
	edge(int x, int y) : u(x), i(y) {}
	operator int() {
		return u;
	}
};
int bs(vector<int> p) {
	auto check = [&](int n) -> ll {
		assert(0 <= n && n <= (int)p.size());
		vector<int> w(p.size(), 0);
		for (int i = 0; i < n; ++i) {
			w[p[i]] = 1;
		}
		return ask(w);
	};
	int lef = -1, rig = (int)p.size();
	ll val = check(rig);
	while (rig - lef > 1) {
		int mid = (lef + rig) / 2;
		if (check(mid) == val) {
			rig = mid;
		} else {
			lef = mid;
		}
	}
	assert(rig - 1 < (int)p.size());
	assert(0 <= rig - 1);
	return p[rig - 1];
}
vector<edge> g[N];
vector<int> bin, bout;
void dfs(int v, int p) {
	for (auto u : g[v]) {
		if (u == p) {
			continue;
		}
		bin.push_back(u.i);
		dfs(u, v);
		bout.push_back(u.i);
	}
}
int d[N];
int p[N];
int e[N];

int far(int from, int x, int y) {
	queue<int> q;
	fill_n(d, N, -1);
	d[from] = 0;
	q.push(from);
	while (q.size()) {
		int v = q.front(); q.pop();
		for (auto u : g[v]) {
			if (d[u] == -1) {
				d[u] = d[v] + 1;
				q.push(u);
			}
		}
	}
	return d[x] > d[y] ? x : y;
}
bool check(int m, int a, int b, int x, int y) {
	queue<int> q;
	fill_n(d, N, -1);
	d[x] = 0;
	q.push(x);
	while (q.size()) {
		int v = q.front(); q.pop();
		for (auto u : g[v]) {
			if (d[u] == -1) {
				d[u] = d[v] + 1;
				p[u] = v;
				e[u] = u.i;
				q.push(u);
			}
		}
	}
	int v = y;
	vector<int> w(m, 0);
	ll d0 = ask(w);
	while (v != x) {
		int i = e[v];
		v = p[v];
		w[i] = 1;
	}
	ll d1 = ask(w);
	// cout << "check " << m << " " << a << " " << b << " " << x << " " << y << endl;
	// cout << "\t\t" << d0 << " " << d1 << " " << d[y] << endl;
	return d0 == a * d[y] && d1 == b * d[y];
}
}

void find_pair(int n, vector<int> u, vector<int> v, int a, int b) {
	using namespace my;
	(void)n;
	assert(a < b);
	int m = (int)u.size();
	for (int i = 0; i < m; ++i) {
		g[v[i]].emplace_back(u[i], i);
		g[u[i]].emplace_back(v[i], i);
	}
	dfs(0, 0);
	int x = bs(bin);
	int y = bs(bout);
	reverse(all(bout));
	int z = bs(bout);

	int fi = far(v[y], v[x], u[x]);
	int se = far(fi, v[y], u[y]);
	if (check(m, a, b, fi, se)) {
		answer(fi, se);
		return;
	}
	fi = far(v[z], v[x], u[x]);
	se = far(fi, v[z], u[z]);
	assert(check(m, a, b, fi, se));
	answer(fi, se);
}

#ifdef LC
#include "grader.cpp"
#endif

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