Submission #818349

#	Time	Username	Problem	Language	Result	Execution time	Memory
818349		pavement	Highway Tolls (IOI18_highway)	C++17	51 / 100	133 ms	14572 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define eb emplace_back
#define mt make_tuple

using ll = long long;
using ii = pair<int, int>;

vector<int> distU, distV, prvU, prvV;
vector<vector<ii> > adj;
queue<int> Q;

void bfs(int s, vector<int> &dist, vector<int> &prv) {
	for (int i = 0; i < (int)dist.size(); i++) {
		dist[i] = (int)1e9;
	}
	dist[s] = 0;
	Q.push(s);
	while (!Q.empty()) {
		int u = Q.front();
		Q.pop();
		for (auto [v, idx] : adj[u]) {
			if (dist[v] > dist[u] + 1) {
				dist[v] = dist[u] + 1;
				prv[v] = idx;
				Q.push(v);
			}
		}
	}
}

void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
	distU.resize(N);
	distV.resize(N);
	prvU.resize(N);
	prvV.resize(N);
	adj.resize(N);
	int M = (int)U.size(), S, T;
	for (int i = 0; i < M; i++) {
		adj[U[i]].eb(V[i], i);
		adj[V[i]].eb(U[i], i);
	}
	ll original = ask(vector<int>(M, 0));
	int lo = 0, hi = M - 1, first_edge = -1;
	while (lo <= hi) {
		int mid = (lo + hi) / 2;
		vector<int> w(M, 0);
		for (int i = 0; i <= mid; i++) {
			w[i] = 1;
		}
		if (ask(w) != original) {
			first_edge = mid;
			hi = mid - 1;
		} else {
			lo = mid + 1;
		}
	}
	assert(first_edge != -1);
	//~ cout << "FE " << first_edge << endl;
	bfs(U[first_edge], distU, prvU);
	bfs(V[first_edge], distV, prvV);
	vector<int> sU, sV, treeU, treeV;
	for (int i = 0; i < N; i++) {
		if (i == U[first_edge] || i == V[first_edge]) continue;
		if (distU[i] < distV[i]) {
			sU.pb(i);
			int prv_node = U[prvU[i]] ^ V[prvU[i]] ^ i;
			if (distU[prv_node] < distV[prv_node]) {
				treeU.pb(prvU[i]);
				//~ cout << "TU " << i << ' ' << prv_node << '\n';
			}
		} else {
			sV.pb(i);
			int prv_node = U[prvV[i]] ^ V[prvV[i]] ^ i;
			if (distU[prv_node] >= distV[prv_node]) {
				treeV.pb(prvV[i]);
				//~ cout << "TV " << i << ' ' << prv_node << '\n';
			}
		}
	}
	
	sort(treeU.begin(), treeU.end());
	assert(unique(treeU.begin(), treeU.end()) == treeU.end());
	sort(treeV.begin(), treeV.end());
	assert(unique(treeV.begin(), treeV.end()) == treeV.end());
	
	vector<int> w(M, 1);
	for (int i : treeV) {
		w[i] = 0;
	}
	w[first_edge] = 0;
	ll tmp = ask(w);
	int U_len = (tmp - original) / (B - A);
	int V_len = original / A - U_len - 1;
	
	vector<int> o_w(M, 1);
	for (int i : treeU) {
		o_w[i] = 0;
	}
	for (int i : treeV) {
		o_w[i] = 0;
	}
	o_w[first_edge] = 0;
	
	for (auto [dist, tree, prv, len, st, R] : {mt(distU, treeU, prvU, U_len, U[first_edge], &S), mt(distV, treeV, prvV, V_len, V[first_edge], &T)}) {
		vector<int> poss;
		if (len == 0 && tree.empty()) {
			poss.pb(st);
		}
		for (int i : tree) {
			if (dist[U[i]] == len) {
				poss.pb(U[i]);
			}
			if (dist[V[i]] == len) {
				poss.pb(V[i]);
			}
		}
		assert(!poss.empty());
		sort(poss.begin(), poss.end());
		poss.erase(unique(poss.begin(), poss.end()), poss.end());
		//~ for (int i : poss) {
			//~ cout << i << ' ';
		//~ }
		//~ cout << '\n';
		while ((int)poss.size() > 1) {
			vector<int> w = o_w;
			for (int i = 0; i < (int)poss.size() / 2; i++) {
				w[prv[poss[i]]] = 1;
			}
			if (ask(w) > original) {
				int new_sz = (int)poss.size() / 2;
				while ((int)poss.size() != new_sz) poss.pop_back();
			} else {
				int new_sz = ((int)poss.size() + 1) / 2;
				reverse(poss.begin(), poss.end());
				while ((int)poss.size() != new_sz) poss.pop_back();
				reverse(poss.begin(), poss.end());
			}
		}
		*R = poss[0];
	}
	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