Submission #544791

#	Time	Username	Problem	Language	Result	Execution time	Memory
544791		rainboy	Treasure Hunt (CEOI11_tre)	C++98	100 / 100	621 ms	76156 KiB

Main

#define N	400000
#define LN	18	/* LN = floor(log2(N)) */

int min(int a, int b) { return a < b ? a : b; }

int ii_[N + 1], dd[N + 1], dd_[N + 1], pp[N + 1][LN + 1], pp_[N + 1][LN + 1], n, n_;

void init() {
	ii_[n] = n_++ + 1, dd[n] = 0, n++;
}

int search(int i_) {
	int lower = 0, upper = n;

	while (upper - lower > 1) {
		int i = (lower + upper) / 2;

		if (ii_[i] <= i_)
			lower = i;
		else
			upper = i;
	}
	return lower;
}

void path(int p_, int sz) {
	int p, l, d;

	ii_[n] = n_ + 1, n_ += sz;
	p = search(p_);
	dd[n] = d = dd[p] + 1, pp[n][0] = p, pp_[n][0] = p_;
	for (l = 1; 1 << l <= d; l++)
		pp[n][l] = pp[pp[n][l - 1]][l - 1], pp_[n][l] = pp_[pp[n][l - 1]][l - 1];
	dd_[n] = dd_[p] + p_ - ii_[p] + 1;
	n++;
}

void get(int i_, int j_, int *d1, int *d2) {
	int i = search(i_), j = search(j_), l;

	if (dd[i] < dd[j]) {
		int tmp, *tmp_;

		tmp = i, i = j, j = tmp, tmp = i_, i_ = j_, j_ = tmp, tmp_ = d1, d1 = d2, d2 = tmp_;
	}
	*d1 = (dd_[i] + i_ - ii_[i]), *d2 = (dd_[j] + j_ - ii_[j]);
	for (l = LN; l >= 0; l--)
		if (dd[i] - dd[j] >= 1 << l)
			i_ = pp_[i][l], i = pp[i][l];
	if (i != j) {
		for (l = LN; l >= 0; l--)
			if (dd[i] >= 1 << l && pp[i][l] != pp[j][l])
				i_ = pp_[i][l], i = pp[i][l], j_ = pp_[j][l], j = pp[j][l];
		i_ = pp_[i][0], i = pp[i][0], j_ = pp_[j][0], j = pp[j][0];
	}
	i_ = min(i_, j_);
	*d1 -= dd_[i] + i_ - ii_[i], *d2 -= dd_[i] + i_ - ii_[i];
}

int ancestor(int i_, int d) {
	int i = search(i_), d_, l;

	d_ = (dd_[i] + i_ - ii_[i]) - d;
	if (dd_[i] > d_) {
		for (l = LN; l >= 0; l--)
			if (dd[i] >= 1 << l && dd_[pp[i][l]] > d_)
				i_ = pp_[i][l], i = pp[i][l];
		i_ = pp_[i][0], i = pp[i][0];
	}
	return ii_[i] + d_ - dd_[i];
}

int dig(int i_, int j_) {
	int d1, d2;

	get(i_, j_, &d1, &d2);
	return d1 >= (d1 + d2) / 2 ? ancestor(i_, (d1 + d2) / 2) : ancestor(j_, d1 + d2 - (d1 + d2) / 2);
}

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