Submission #294955

#	Time	Username	Problem	Language	Result	Execution time	Memory
294955		RealSuperman1	Highway Tolls (IOI18_highway)	C++14	51 / 100	347 ms	262148 KiB

highway

#pragma GCC optimize("Ofast")

#include <bits/stdc++.h>
#include "highway.h"
#define ll long long
#define fi first
#define se second
#define pb push_back
#define pll pair<long long, long long>
#define pii pair<int, int>

using namespace std;

//const int N = 2e5 + 10;

int n, m, max_height = 0, timer;
vector < vector <pii> > g;
vector < vector <int> > fixed_h;
vector <int> h, tin, tout;
vector <pii> par;

void dfs(int u, int p, int id_w, int height) {
	tin[u] = ++timer;
	max_height = max(max_height, height);
	h[u] = height;
	par[u] = {p, id_w};
	for (auto to : g[u])
		if (to.fi != p)
			dfs(to.fi, u, to.se, h[u] + 1);
	tout[u] = ++timer;
}

bool parent(int par, int u) {
	return (tin[par] <= tin[u] && tout[par] >= tout[u]);
}

ll find_val() {
	vector <int> w(m, 0);
	return ask(w);
}

int find_lower_level(ll val) {
	int L = 0, R = max_height, M, ans = 0;
	vector <int> w;
	while (L <= R) {
		M = (L + R) / 2;
		w.assign(m, 0);
		for (int height = M; height <= R; height++)
			for (int to : fixed_h[height]) {
				if (par[to].se >= 0)
					w[par[to].se] = 1;
			}
		ll curval = ask(w);
		if (curval > val) {
			L = M + 1;
			ans = max(ans, M);
		} else {
			R = M - 1;
		}
	}
	return ans;
}

int get_answer(vector <int> candidates, ll val) {
	vector <int> L, R, w;
	while (candidates.size() > 1) {
		L.clear(); R.clear();
		w.assign(m, 0);
		int lim = candidates.size() / 2;
		for (int i = 0; i < lim; i++) {
			int u = candidates[i];
			L.pb(u);
			if (par[u].se >= 0)
				w[par[u].se] = 1;
		}
		for (int i = lim; i < candidates.size(); i++) {
			R.pb(candidates[i]);
		}
		ll curval = ask(w);
		if (curval > val)
			candidates = L;
		else
			candidates = R;
	}
	return candidates[0];
}

int solve_from(int C, int dist, ll val) {
	max_height = 0; timer = 0;
	dfs(C, -1, -1, 0);
	fixed_h.resize(max_height + 1);
	for (int i = 0; i <= max_height; i++)
		fixed_h[i].clear();
	for (int i = 0; i < n; i++)
		fixed_h[h[i]].pb(i);
	return get_answer(fixed_h[dist], val);
}

void find_pair(int n1, vector <int> U, vector <int> V, int A, int B) {
	n = n1;
	m = U.size();
	g.resize(n);
	h.resize(n);
	par.resize(n);
	tin.resize(n);
	tout.resize(n);
	for (int i = 0; i < m; i++) {
		g[U[i]].pb({V[i], i});
		g[V[i]].pb({U[i], i});
	}
	timer = 0;
	dfs(0, -1, -1, 0);
	fixed_h.resize(max_height + 1);
	for (int i = 0; i < n; i++)
		fixed_h[h[i]].pb(i);
	ll val = find_val();
	int dist = val / (A * 1ll);
	int lower_level = find_lower_level(val);
	int C = get_answer(fixed_h[lower_level], val);
	int T = solve_from(C, dist, val);
//	cout << C << " " << T << endl;
	answer(C, T);
}

Compilation message (stderr)

highway.cpp: In function 'int get_answer(std::vector<int>, long long int)':
highway.cpp:76:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |   for (int i = lim; i < candidates.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~~~~~

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