Submission #817827

#	Time	Username	Problem	Language	Result	Execution time	Memory
817827		pavement	Highway Tolls (IOI18_highway)	C++17	51 / 100	137 ms	35580 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>;

int ed;
vector<int> ndep;
vector<vector<int> > U_edges, V_edges;
vector<vector<ii> > adj;

void dfs(int u, vector<vector<int> > &edges, int dep = 0, int e = -1) {
	ndep[u] = dep;
	for (auto [v, idx] : adj[u]) if (v != e && idx != ed) {
		edges[dep].pb(idx);
		dfs(v, edges, dep + 1, u);
	}
}

void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
	ndep.resize(N);
	adj.resize(N);
	int M = (int)U.size();
	vector<int> cur;
	for (int i = 0; i < M; i++) {
		adj[U[i]].eb(V[i], i);
		adj[V[i]].eb(U[i], i);
		cur.pb(i);
	}
	ll original = ask(vector<int>(M, 0));
	while ((int)cur.size() > 1) {
		vector<int> w(M, 0);
		for (int i = 0; i < (int)cur.size() / 2; i++) {
			w[cur[i]] = 1;
		}
		if (ask(w) > original) {
			int new_sz = (int)cur.size() / 2;
			while ((int)cur.size() != new_sz) cur.pop_back();
		} else {
			int new_sz = ((int)cur.size() + 1) / 2;
			reverse(cur.begin(), cur.end());
			while ((int)cur.size() != new_sz) cur.pop_back();
			reverse(cur.begin(), cur.end());
		}
	}
	ed = cur[0];
	U_edges.resize(N);
	V_edges.resize(N);
	dfs(U[ed], U_edges);
	dfs(V[ed], V_edges);
	vector<int> w(M, 0);
	for (auto edges_by_dep : U_edges) {
		for (auto edge : edges_by_dep) {
			w[edge] = 1;
		}
	}
	ll tmp = ask(w);
	int U_len = (tmp - original) / (B - A);
	int V_len = original / A - U_len - 1;
	int S, T;
	for (auto [len, edges, R, W] : {mt(U_len, U_edges, &S, U), mt(V_len, V_edges, &T, V)}) {
		if (len) {
			vector<int> cur = edges[len - 1];
			while ((int)cur.size() > 1) {
				vector<int> w(M, 0);
				for (int i = 0; i < (int)cur.size() / 2; i++) {
					w[cur[i]] = 1;
				}
				if (ask(w) > original) {
					int new_sz = (int)cur.size() / 2;
					while ((int)cur.size() != new_sz) cur.pop_back();
				} else {
					int new_sz = ((int)cur.size() + 1) / 2;
					reverse(cur.begin(), cur.end());
					while ((int)cur.size() != new_sz) cur.pop_back();
					reverse(cur.begin(), cur.end());
				}
			}
			*R = (ndep[U[cur[0]]] > ndep[V[cur[0]]] ? U[cur[0]] : V[cur[0]]);
		} else {
			*R = W[ed];
		}
	}
	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