Submission #294766

#	Time	Username	Problem	Language	Result	Execution time	Memory
294766		RealSuperman1	Highway Tolls (IOI18_highway)	C++14	6 / 100	147 ms	19480 KiB

highway

#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_height_lca(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);
//		cout << "Cur " << M << endl;
		for (int height = 0; height <= M; height++)
			for (int to : fixed_h[height]) {
				if (par[to].se >= 0)
					w[par[to].se] = 1;
//				cout << height << " " << to << " " << par[to].fi << " " << par[to].se << endl;
			}
		ll curval = ask(w);
		if (curval > val) {
			R = M - 1;
		} else {
			ans = max(ans, M);
			L = M + 1;
		}
	}
	return ans;
}

int get_answer(vector <int> candidates, ll val) {
	vector <int> L, R, w;
//	cout << "Dsdf " << endl;
	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]);
		}
//		cout << "L ";
//		for (int to : L)
//			cout << to << " ";
//		cout << endl << "R ";
//		for (int to : R)
//			cout << to << " ";
//		cout << endl;
		ll curval = ask(w);
//		cout << "curval " << curval << endl;
		if (curval > val)
			candidates = L;
		else
			candidates = R;
	}
	return candidates[0];
}

vector <int> get_candidates(int u, int height) {
	vector <int> ans = {};
	for (int to : fixed_h[height])
		if (parent(u, to))
			ans.pb(to);
	return ans;
}

int find_lca(int height, ll val) {
	return get_answer(get_candidates(1, height), val);
}

int find_first_end(int lca, int dist, ll val) {
	int L = h[lca] + (dist + 1) / 2, R = min(max_height, h[lca] + dist), M, ch = h[lca];
//	cout << L << " " << R << endl;
	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) {
			ch = max(ch, M);
			L = M + 1;
		} else
			R = M - 1;
	}
//	cout << "max_heihgt c " << ch << endl;
//	vector <int> cur = get_candidates(lca, ch);
//	for (int to : cur)
//		cout << to << " ";
//	cout << endl;
	return get_answer(get_candidates(lca, ch), 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);
	if (m != n - 1) {
		answer(0, 1);
		return;
	}
	for (int i = 0; i < m; i++) {
		g[U[i]].pb({V[i], i});
		g[V[i]].pb({U[i], i});
	}
//	return;
	timer = 0;
	dfs(1, -1, -1, 0);
//	return;
	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);
//	cout << dist << " " << val << endl;
	int height_lca = find_height_lca(val);
//	cout << "heihgt " << height_lca << endl;
	int lca = find_lca(height_lca, val);
//	cout << "lca " << lca << endl;
	int C = find_first_end(lca, dist, val);
//	cout << "C " << C << endl;
	int remain_dist = dist - (h[C] - h[lca]);
	if (remain_dist == 0) {
		answer(C, lca);
		return;
	}
	vector <int> candidates = {};
	for (auto cur : g[lca]) {
		int to = cur.fi;
		if (par[lca].fi == to || (parent(to, C)))
			continue;
		vector <int> tmp = get_candidates(to, h[lca] + remain_dist);
		for (int x : tmp)
			candidates.pb(x);
	}
//	cout << "kldsf 0" << endl;
//	for (int to : candidates)
//		cout << to << " ";
//	cout << endl;
	int T = get_answer(candidates, val);
//	cout << "T " << T << endl;
	answer(C, T);
}

Compilation message (stderr)

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

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