Submission #294910

#	Time	Username	Problem	Language	Result	Execution time	Memory
294910		RealSuperman1	Highway Tolls (IOI18_highway)	C++14	18 / 100	3076 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, root;
vector < vector <pii> > g;
vector < vector <int> > fixed_h;
vector <int> h, tin, tout;
vector <pii> par;


pii getmax(int u, int p, int dist) {
	pii mx = {dist, u};
	for (auto to : g[u]) {
		if (to.fi == p)
			continue;
		pii tmp = getmax(to.fi, u, dist + 1);
		if (tmp.fi > mx.fi)
			mx = tmp;		
	}
	return mx;
}

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);
		for (int height = 0; height <= M; height++)
			for (int to : fixed_h[height]) {
				if (par[to].se >= 0)
					w[par[to].se] = 1;
			}
		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, bool flag=false) {
	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 (!flag) {
				for (auto to : g[u])
					if (par[u].fi != to.fi)
						w[to.se] = 1;
			} else {
				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];
}

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(root, 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];
	vector < vector <int> > fixed_h_cur;
	fixed_h_cur.resize(max_height + 1);
	for (int i = 0; i <= max_height; i++)
		for (int to : fixed_h[i])
			if (parent(lca, to))
				fixed_h_cur[i].pb(to); 
	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_cur[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;
	}
	return get_answer(get_candidates(lca, ch), val, true);
}

int get_middle(int u, int v) {
	vector <int> a1 = {}, a2 = {};
	int cur = u;
	while (true) {
		a1.pb(cur);
		if (parent(cur, v))
			break;
		cur = par[cur].fi;
	}
	cur = v;
	while (true) {
		if (parent(cur, u))
			break;
		a2.pb(cur);
		cur = par[cur].fi;
	}
	reverse(a2.begin(), a2.end());
	for (int to : a2)
		a1.pb(to);
	return a1[a1.size() / 2];
}

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);
	pii t1 = getmax(0, -1, 0);
	pii t2 = getmax(t1.se, -1, 0);
//	cout << t1.se << " " << t2.se << endl;
	root = get_middle(t1.se, t2.se);
//	cout << root << ndl;
	timer = 0;
	dfs(root, -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 height_lca = find_height_lca(val);
	
	int lca = find_lca(height_lca, val);
	int C = find_first_end(lca, dist, val);
	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);
	}
	int T = get_answer(candidates, val, true);
	answer(C, T);
}

Compilation message (stderr)

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

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