oj.uz

Submission #544791

# Submission time Handle Problem Language Result Execution time Memory
544791 2022-04-02T16:47:58 Z rainboy Treasure Hunt (CEOI11_tre) C++
100 / 100
 621 ms 76156 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 468 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 468 KB Output is correct
2 Correct 3 ms 852 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 392 ms 64260 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 468 ms 20572 KB Output is correct
2 Correct 265 ms 46116 KB Output is correct
3 Correct 244 ms 46200 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 503 ms 46096 KB Output is correct
2 Correct 317 ms 17148 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 621 ms 46064 KB Output is correct
2 Correct 403 ms 46076 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 15692 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 376 ms 46108 KB Output is correct
2 Correct 252 ms 76156 KB Output is correct
3 Correct 193 ms 76104 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 460 ms 46148 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 446 ms 46120 KB Output is correct