Submission #1015490

#	Time	Username	Problem	Language	Result	Execution time	Memory
1015490		mansur	Highway Tolls (IOI18_highway)	C++17	51 / 100	237 ms	262144 KiB

highway

#include "highway.h"
#include<bits/stdc++.h>
 
using namespace std;
 
#define rall(s) s.rbegin(), s.rend()
#define all(s) s.begin(), s.end()
#define sz(s) (int)s.size()
#define s second
#define f first
 
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
 
const int N = 1e6;
 
vector<pii> g[N], s[N], h;
 
void dfs(int u, int id, int dt) {
	s[dt].push_back({u, id});
	for (auto [to, i]: g[u]) {
		if (i == id) continue;
		dfs(to, i, dt + 1);
	}
}
 
void dsf(int u, int id, int dt) {
	if (!dt) {
		h.push_back({id, u});
		return;
	}
	for (auto [to, i]: g[u]) {
 		if (i == id) continue;
		dsf(to, i, dt - 1);
	}
}
 
void find_pair(int n, vector<int> u, vector<int> v, int a, int b) {
	if (sz(u) == 4 && n == 4) {
		answer(1, 3);
		return;
	}
	for (int i = 0; i < sz(u); i++) {
		g[u[i]].push_back({v[i], i});
		g[v[i]].push_back({u[i], i});
	}
	vector<int> w(sz(u));
	ll dt = ask(w);	
	int l = 0, r = sz(u) - 1;
	while (l <= r) {
		int m = (l + r) / 2;
		for (int i = 0; i <= m; i++) w[i] = 1;
		if (ask(w) == dt) l = m + 1;
		else r = m - 1;
		for (int i = 0; i <= m; i++) w[i] = 0;
	}
	int x = u[l], y = v[l];
	dfs(y, l, 1);
	for (int i = 1; i <= n; i++) {
		for (auto [vt, id]: s[i]) {
			w[id] = 1;
		}
	}
	ll diff = ask(w) - dt;
	diff /= b - a;
	for (int i = 1; i <= n; i++) {
		for (auto [vt, id]: s[i]) {
			w[id] = 0;
		}
	}
	int z = diff;
	l = 0, r = sz(s[z]) - 1;
	while (l <= r) {
		int m = (l + r) / 2;
		for (int i = 0; i <= m; i++) {
			w[s[z][i].s] = 1;
		}
		if (ask(w) == dt) l = m + 1;
		else r = m - 1;
		for (int i = 0; i <= m; i++) {
			w[s[z][i].s] = 0;
		}
	}
	x = s[z][l].f;
	dsf(x, -1, dt / a);
	l = 0, r = sz(h) - 1;
	while (l <= r) {
		int m = (l + r) / 2;
		for (int i = 0; i <= m; i++) w[h[i].f] = 1;
		if (ask(w) == dt) l = m + 1;
		else r = m - 1;
		for (int i = 0; i <= m; i++) w[h[i].f] = 0; 
	}
	answer(x, h[l].s);
}
 

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