Submission #1201871

#	Time	Username	Problem	Language	Result	Execution time	Memory
1201871		alind	Highway Tolls (IOI18_highway)	C++20	0 / 100	7 ms	2064 KiB

highway

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

using namespace std;

typedef long long ll;

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
	int M = U.size();
	vector<vector<pair<int, int>>> gr(N);
	for (int i = 0; i < M; i++) {
		gr[V[i]].push_back({U[i], i});
		gr[U[i]].push_back({V[i], i});
	}
	vector<int> w(M, 0);
	ll shrt = ask(w);
	int rt = 0, j = 1<<20;
	while (j) {
		if (rt + j <= N) {
			w.assign(M, 0);
			for (int i = rt; i < rt + j; i++)
				for (auto [u, k] : gr[i])
					w[k] = 1;
			if (ask(w) == shrt) rt += j;
		}
		j >>= 1;
	}
	vector<int> pa(N, -1), cnt(N, 0), ei(N, -1), vis(N, 0);
	queue<int> q, lf;
	q.push(rt); vis[rt] = 1;
	while (q.size()) {
		int v = q.front(); q.pop();
		for (auto [u, i] : gr[v]) if (!vis[u]) {
			cnt[v]++;
			vis[u] = 1;
			pa[u] = v;
			ei[u] = i;
			q.push(u);
		}
		if (!cnt[v]) lf.push(v);
	}
	vector<int> ord;
	while (lf.size()) {
		int v = lf.front(); lf.pop();
		ord.push_back(v);
		if (!--cnt[pa[v]]) lf.push(pa[v]);
	}
	assert (ord.back() == rt);
	int s = 0; j = 1<<20;
	while (j) {
		if (s + j < N) {
			w.assign(M, 0);
			for (int i = s; i < s + j; i++) w[ei[ord[i]]] = 1;
			if (ask(w) == shrt) s += j;
		}
		j >>= 1;
	}
	s = ord[s];
	vector<int> dis(N, 1<<30); dis[s] = 0;
	vector<int> cand;
	vector<vector<int>> from(N);
	q.push(s);
	while (q.size()) {
		int v = q.front(); q.pop();
		if (1ll * dis[v] * A == shrt) cand.push_back(v);
		for (auto [u, i] : gr[v]) if (dis[u] > dis[v]) {
			dis[u] = dis[v] + 1;
			from[u].push_back(i);
			q.push(u);
		}
	}
	assert (cand.size());
	int t = 0;
	j = 1<<20; 
	while (j) {
		if (t + j < (int)cand.size()) {
			w.assign(M, 0);
			for (int i = t; i < t + j; i++)
				for (auto k : from[cand[i]])
					w[k] = 1;
			if (ask(w) == shrt) t += j;
		}
		j >>= 1;
	}
	t = cand[t];
	answer(s, t);
}

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