Submission #415694

#	Time	Username	Problem	Language	Result	Execution time	Memory
415694		SuhaibSawalha1	Highway Tolls (IOI18_highway)	C++17	51 / 100	326 ms	262148 KiB

highway

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

vector<vector<array<int, 2>>> adj;
vector<array<int, 2>> to_ask;
vector<int> ak;
int n, m, A, B, dp;
long long W;

void dfs (int u, int p, int d = 1) {
	for (auto &v : adj[u]) {
		if (v[0] ^ p) {
			if (d == dp) {
				to_ask.push_back(v);
			}	
			else {
				dfs(v[0], u, d + 1);
			}
		}
	}
}

void dfs2 (int u, int p) {
	for (auto &v : adj[u]) {
		if (v[0] ^ p) {
			ak[v[1]] = 1;
			dfs2(v[0], u);
		}
	}
}

int first () {
	int l = 0, r = m - 1;
	W = ask(vector<int>(m, 0));
	while (l < r) {
		int mid = (l + r) / 2;
		vector<int> ak(m, 0);
		fill(ak.begin(), ak.begin() + mid + 1, 1);
		if (ask(ak) != W) {
			r = mid;
		}
		else {
			l = mid + 1;
		}
	}
	return l;
}



void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
	n = N;
	m = U.size();
	::A = A;
	::B = B;
	adj.assign(n, {});
	for (int i = 0; i < m; ++i) {
		adj[U[i]].push_back({V[i], i});
		adj[V[i]].push_back({U[i], i});
	}	
	int f = first();
	int u = U[f], v = V[f];
	ak.assign(m, 0);
	dfs2(u, v);
	long long WE = ask(ak);
	int s = W / A;
	auto go = [&] (int u, int v, int dp) {
		if (!dp) {
			return u;
		}
		::dp = dp;
		to_ask.clear();
		dfs(u, v);
		int l = 0, r = to_ask.size() - 1;
		while (l < r) {
			int mid = (l + r) / 2;
			vector<int> ak(m, 0);
			for (int i = 0; i <= mid; ++i) {
				ak[to_ask[i][1]] = 1;
			}
			if (ask(ak) != s * 1LL * A) {
				r = mid;
			}
			else {
				l = mid + 1;
			}
		}
		return to_ask[l][0];
	};
	for (int i = 0; i <= s; ++i) {
		if (i * 1LL * A + (s - i) * 1LL * B == WE) {
			return answer(go(u, v, s - i), go(v, u, i - 1));
		}
	}
	assert(0);
}	

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