Submission #294684

#	Time	Username	Problem	Language	Result	Execution time	Memory
294684		SeDunion	Highway Tolls (IOI18_highway)	C++14	0 / 100	3069 ms	73084 KiB

highway

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

int M;
ll Ask (vector<int> v) {
	vector<int> w(M);
	for (int i : v) w[i] = 1;
	return ask (w);
}
const int N = 2e5;
vector<pair<int,int>> g[N], mb, h[N];

void dfs (int v, int d = 0, int p = -1) {
	for (auto [to, i] : g[v]) if (to != p) {
		h[d].push_back ({to, i});
		dfs (to, d + 1, v);
	}
}

void dfs2 (int v, ll d, int p = -1) {
	for (auto [to, i] : g[v]) if (to != p) {
		if (d == 1) {
			mb.push_back ({to, i});
		} else {
			dfs2 (to, d-1, v);
		}
	}
}

void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
	M = U.size();
	for (int i = 0 ; i < M ; ++ i) {
		g[U[i]].push_back ({V[i], i});
		g[V[i]].push_back ({U[i], i});
	}
	ll dist = Ask ({}) / A;
	dfs(0);
	int l = 0, r = 0, ans = -1;
	while (h[r + 1].size()) ++r;
	while (l <= r) {
		int m = (l + r) >> 1;
		vector<int>now;
		for (int j = l ; j <= m ; ++ j) {
			for (auto [v, i] : h[j]) {
				now.push_back (i);
			}
		}
		if (Ask(now) == dist * B) {
			r = m - 1;
		} else {
			// cerr << Ask(now) << ' ' << dist * A << " a\n";
			ans = m;
			l = m + 1;
		}
	}
	if (ans == -1) while(1);
	assert (ans != -1);
	if (h[ans].empty()) while(1);
	assert (h[ans].size());
	mb.clear();
	for (auto [v, i] : h[ans]) {
		mb.push_back ({v, i});
	}
	if (mb.empty()) while(1);
	assert (mb.size());
	l = 0, r = int(mb.size()) - 1, ans = -1;
	while (l <= r) {
		int m = (l + r) >> 1;
		vector<int> now;
		for (int i = l ; i <= m ; ++ i) {
			now.push_back (mb[i].second);
		}
		if (Ask(now) > dist * A) {
			ans = m;
			r = m - 1;
		} else {
			l = m + 1;
		}
	}
	if (ans == -1) while(1);
	assert (ans != -1);
	int S = mb[ans].first;
	mb.clear();
	dfs2 (S, dist);
	l = 0, r = int(mb.size()) - 1;
	while (l < r) {
		int m = (l + r) >> 1;
		vector<int>now;
		for (int i = l ; i <= m ; ++ i) {
			now.push_back (mb[i].second);
		}
		if (Ask(now) > dist * A) {
			r = m;
		} else {
			l = m + 1;
		}
	}
	answer (S, mb[r].first);
}

Compilation message (stderr)

highway.cpp: In function 'void dfs(int, int, int)':
highway.cpp:16:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   16 |  for (auto [to, i] : g[v]) if (to != p) {
      |            ^
highway.cpp: In function 'void dfs2(int, ll, int)':
highway.cpp:23:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   23 |  for (auto [to, i] : g[v]) if (to != p) {
      |            ^
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:46:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   46 |    for (auto [v, i] : h[j]) {
      |              ^
highway.cpp:63:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   63 |  for (auto [v, i] : h[ans]) {
      |            ^

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