Submission #414989

#	Time	Username	Problem	Language	Result	Execution time	Memory
414989		SuhaibSawalha1	Highway Tolls (IOI18_highway)	C++17	18 / 100	293 ms	8312 KiB

highway

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

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

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

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, {});
	bool subtask3 = 1;
	for (int i = 0; i < m; ++i) {
		adj[U[i]].push_back({V[i], i});
		adj[V[i]].push_back({U[i], i});
		subtask3 &= U[i] == i && V[i] == i + 1;
	}	
	dp = ask(vector<int>(m, 0)) / A;
	if (subtask3) {
		int l = 0, r = m - 1;
		while (l < r) {
			int mid = (l + r + 1) / 2;
			vector<int> ak(m, 1);
			fill(ak.begin(), ak.begin() + mid, 0);
			if (ask(ak) == B * 1LL * dp) {
				l = mid;
			}	
			else {
				r = mid - 1;
			}
		}
		return answer(l, l + dp);
	}
	dfs();
	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) != dp * 1LL * A) {
			r = mid;
		}
		else {
			l = mid + 1;
		}
	}
	answer(0, to_ask[l][0]);
}	

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