Submission #118344

#	Time	Username	Problem	Language	Result	Execution time	Memory
118344		Bruteforceman	Treasure Hunt (CEOI11_tre)	C++11	10 / 100	1827 ms	62840 KiB

Main

#include "bits/stdc++.h"
using namespace std;

int current_point;
int node;

int link[400010];
int id[400010];
int len[400010];

map <int, int> mp;
set <int> s;
int anc[20][400010];

int dep[400010], dist[400010];

const int logn = 19;

void init()
{
	s.clear();
	mp.clear();
	node = 1;
	current_point = 1;
	
	id[1] = 1;
	len[1] = 0;
	link[1] = -1;
	mp[1] = node;
	s.insert(1);
}

void path(int a, int sq)
{
	current_point += sq;
	id[++node] = current_point;
	len[node] = sq;
	link[node] = a;
	mp[current_point] = node;
	s.insert(current_point);

	int par = mp[*s.lower_bound(a)];
	anc[0][node] = par;

	dep[node] = dep[par] + 1;
	dist[node] = dist[par] + len[par] - (id[par] - a);

	for(int i = 1; i <= logn; i++) {
		anc[i][node] = anc[i - 1][anc[i - 1][node]];
	}
}

int find_node(int x) {
	return mp[*s.lower_bound(x)];
}

int lca(int p, int q) {
	if(dep[p] > dep[q]) swap(p, q);
	for(int i = logn; i >= 0; i--) {
		if(dep[q] - (1 << i) >= dep[p]) {
			q = anc[i][q];
		}
	}
	if(p == q) return p;
	for(int i = logn; i >= 0; i--) {
		if(anc[i][p] != anc[i][q]) {
			p = anc[i][p];
			q = anc[i][q];
		}
	}
	return anc[0][p];
}

int lift(int p, int deep) {
	for(int i = logn; i >= 0; i--) {
		if(dep[p] - (1 << i) >= deep) {
			p = anc[i][p];
		}
	}
	return p;
}


int distance(int p, int q) {
	int s = find_node(p);
	int t = find_node(q);
	int pr = lca(s, t);

	int lp, lq;
	long long ans = dist[s] + dist[t] - 2 * dist[pr];

	ans += len[s] - abs(id[s] - p);
	ans += len[t] - abs(id[t] - q);

	lp = (s == pr) ? p : link[lift(s, dep[pr] + 1)];
	lq = (t == pr) ? q : link[lift(t, dep[pr] + 1)];

	ans -= len[pr] - abs(id[pr] - min(lp, lq));
	ans -= len[pr] - abs(id[pr] - min(lp, lq));
	return ans;
}

int move_up(int x, int up) {
	int s = find_node(x);
	int nxt_dist = len[s] - abs(id[s] - x);
	if(nxt_dist > up) {
		return x - up;
	}
	up -= nxt_dist;
	for(int i = logn; i >= 0; i--) {
		if(dep[s] < (1 << i)) continue;
		int p = anc[i][s];
		if(dist[s] - dist[p] < up) {
			up -= dist[s] - dist[p];
			s = p;
		}
	}
	s = link[s];
	return s - up;
}

int dig(int p, int q)
{
	int s = find_node(p);
	int t = find_node(q);
	int pr = lca(s, t);
	int lp, lq;
	lp = (s == pr) ? p : link[lift(s, dep[pr] + 1)];
	lq = (t == pr) ? q : link[lift(t, dep[pr] + 1)];

	int tot = distance(p, q);
	int med = tot / 2;
	if(med <= distance(p, lp)) {
		return move_up(p, med);
	}
	med -= distance(p, lp);
	if(med <= abs(lp - lq)) {
		if(lp < lq) return lp + med;
		else return lp - med;
	}
	med -= abs(lp - lq);
	return move_up(q, distance(q, lq) - med);
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 10 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10