Submission #298153

#	Time	Username	Problem	Language	Result	Execution time	Memory
298153		keko37	Highway Tolls (IOI18_highway)	C++14	51 / 100	312 ms	262148 KiB

highway

#include<bits/stdc++.h>
#include "highway.h"

using namespace std;

typedef long long llint;
typedef pair <int, int> pi;
typedef vector <int> vi;

const int MAXN = 90005;
const int MAXM = 150005;

llint n, m, a, b, L;
int ea[MAXM], eb[MAXM];
int bio[MAXN], pe[MAXN], par[MAXN];
vector <pi> v[MAXN];

///////////////////////////////////////

llint pitaj (vi e) {
	vi q(m);
	for (auto i : e) q[i] = 1;
	return ask(q);
}

int overlap (vi e) {
	llint res = pitaj(e);
	return (res - L * a) / (b - a);
}

int get_length () {
	vector <int> e;
	return pitaj(e) / a;
}

///////////////////////////////////////

int dub, R;
vector <int> nodes, edges;

void get_nodes_at_depth (int x, int rod, int curr) {
	if (curr == dub) nodes.push_back(x);
	par[x] = rod;
	for (auto pp : v[x]) {
		int sus = pp.first, ind = pp.second;
		if (sus == rod) {
			pe[x] = ind;
			continue;
		}
		get_nodes_at_depth(sus, x, curr + 1);
	}
}

void climb (int x) {
	while (1) {
		if (bio[x]) break;
		bio[x] = 1;
		if (x == R) break;
		edges.push_back(pe[x]);
		x = par[x];
	}
}

int find_node (vi curr) {
	if (curr.size() == 1) return curr[0];
	int siz = curr.size();
	vi lo, hi;
	for (int i = 0; i < siz; i++) {
		if (i * 2 < siz) lo.push_back(curr[i]); else hi.push_back(curr[i]);
	}
	edges.clear();
	memset(bio, 0, sizeof bio);
	for (auto x : lo) climb(x);
	if (overlap(edges) == dub) return find_node(lo);
	return find_node(hi);
}

int solve_subtree (int root, int rod, int len) {
	nodes.clear(); dub = len; R = root;
	get_nodes_at_depth(root, rod, 0);
	return find_node(nodes);
}

///////////////////////////////////////

pi find_edge (vi curr) {
	if (curr.size() == 1) return {ea[curr[0]], eb[curr[0]]};
	int siz = curr.size();
	vi lo, hi;
	for (int i = 0; i < siz; i++) {
		if (i * 2 < siz) lo.push_back(curr[i]); else hi.push_back(curr[i]);
	}
	if (overlap(lo) > 0) return find_edge(lo);
	return find_edge(hi);
}

void subtree_edges (int x, int rod) {
	for (auto pp : v[x]) {
		int sus = pp.first, ind = pp.second;
		if (sus == rod) continue;
		edges.push_back(ind);
		subtree_edges(sus, x);
	}
}

///////////////////////////////////////

void find_pair (int N, vi U, vi V, int A, int B) {
	n = N; m = U.size(), a = A, b = B;
	for (int i = 0; i < m; i++) {
		ea[i] = U[i], eb[i] = V[i];
		v[U[i]].push_back({V[i], i});
		v[V[i]].push_back({U[i], i});
	}
	L = get_length();
	vi curr_edges;
	for (int i = 0; i < m; i++) curr_edges.push_back(i);
	pi res = find_edge(curr_edges);
	int ra = res.first, rb = res.second;
	edges.clear();
	subtree_edges(ra, rb);
	int len = overlap(edges);
	answer(solve_subtree(ra, rb, len), solve_subtree(rb, ra, L - len - 1));
}

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