oj.uz

Submission #872754

# Submission time Handle Problem Language Result Execution time Memory
872754 2023-11-13T16:39:29 Z vjudge1 Ball Machine (BOI13_ballmachine) C++17
100 / 100
 673 ms 38908 KB 
#include<bits/stdc++.h>
using namespace std;
 
#define F first
#define S second
#define pii pair<int, int>
#define pb push_back
#define pp pop_back
#define all(x) x.begin(), x.end()
 
const int N = 1e5 + 12, M = 20;
vector<int> g[N];
int n, q, t, f[N], p[N], par[M][N], root, d[N], seg[4 * N], lazy[4 * N], ls[4 * N], h[N];
pii pl[4 * N];
 
void ip() {
	cin >> n >> q;
	for (int i = 0; i < n; i++) {
		int u;
		cin >> u;
		u--;
		par[0][i] = u;
		if (u == -1)
			root = i;
		else {
			g[u].pb(i);
			g[i].pb(u);
		}
	}
	par[0][root] = root;
}
 
void dfs1(int u) {
	d[u] = u;
	for (auto i: g[u])
		if (i != par[0][u]) {
			h[i] = h[u] + 1;
			dfs1(i);
			d[u] = min(d[u], d[i]);
		}
}
 
void dfs2(int u) {
	vector<pii> tmp;
	for (auto i: g[u])
		if (i != par[0][u])
			tmp.pb({d[i], i});
	sort(all(tmp));
	for (auto i: tmp)
		dfs2(i.S);
	f[t] = u;
	p[u] = t;
	t++;
}
 
void pre() {
	dfs1(root);
	dfs2(root);
	for (int i = 1; i < M; i++)
		for (int j = 0; j < n; j++)
			par[i][j] = par[i - 1][par[i - 1][j]];
}
 
void shift(int id) {
	if (ls[id * 2] < ls[id]) {
		seg[id * 2] = lazy[id] * (pl[id * 2].S - pl[id * 2].F);
		lazy[id * 2] = lazy[id];
		ls[id * 2] = ls[id];
	}
	if (ls[id * 2 + 1] < ls[id]) {
		lazy[id * 2 + 1] = lazy[id];
		seg[id * 2 + 1] = lazy[id] * (pl[id * 2 + 1].S - pl[id * 2 + 1].F); 
		ls[id * 2 + 1] = ls[id];
	}
}
 
void add(int l, int r, int x, int w, int id = 1) {
	if (l <= pl[id].F && r >= pl[id].S) {
		lazy[id] = x;
		seg[id] = x * (pl[id].S - pl[id].F);
		ls[id] = w;
		return;
	}
	if (r <= pl[id].F || l >= pl[id].S) 
		return;
	shift(id);
	add(l, r, x, w, id * 2);
	add(l, r, x, w, id * 2 + 1);
	seg[id] = seg[id * 2] + seg[id * 2 + 1];
}
 
int ask(int l, int r, int id = 1) {
	if (l <= pl[id].F && r >= pl[id].S) 
		return seg[id];
	if (r <= pl[id].F || l >= pl[id].S) 
		return 0;
	shift(id);
	int res = ask(l, r, id * 2) + ask(l, r, id * 2 + 1);
	seg[id] = seg[id * 2] + seg[id * 2 + 1];
	return res;
}
 
void query() {
	int w = 1;
	pl[1] = {0, n};
	for (int i = 1; i < 2 * n; i++) {
		int mid = (pl[i].F + pl[i].S) / 2;
		pl[i * 2] = {pl[i].F, mid};
		pl[i * 2 + 1] = {mid, pl[i].S};
	}
	while (q--) {
		int u, v;
		cin >> u >> v;
		if (u == 1) {
			int l = -1, r = n;
			while (r - l > 1) {
				int mid = (l + r) / 2;
				if (mid + 1 - ask(0, mid + 1) < v)
					l = mid;
				else
					r = mid;
			}
			cout << f[r] + 1 << '\n';
			add(0, r + 1, 1, w++);
		}
		else {
			v--;
			int z = v;
			for (int i = M - 1; ~i; i--)
				if (ask(p[par[i][v]], p[par[i][v]] + 1))
					v = par[i][v];
			cout << h[z] - h[v] << '\n';
			add(p[v], p[v] + 1, 0, w++);
		}
	}
}
 
int32_t main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	ip(), pre(), query();
	return 0;
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 15708 KB Output is correct
2 Correct 510 ms 20724 KB Output is correct
3 Correct 333 ms 20560 KB Output is correct
4 Correct 3 ms 15708 KB Output is correct
5 Correct 3 ms 15708 KB Output is correct
6 Correct 4 ms 15832 KB Output is correct
7 Correct 4 ms 15764 KB Output is correct
8 Correct 5 ms 15708 KB Output is correct
9 Correct 24 ms 15964 KB Output is correct
10 Correct 67 ms 18684 KB Output is correct
11 Correct 420 ms 21048 KB Output is correct
12 Correct 318 ms 20560 KB Output is correct
13 Correct 363 ms 20528 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 21588 KB Output is correct
2 Correct 565 ms 31132 KB Output is correct
3 Correct 287 ms 22912 KB Output is correct
4 Correct 278 ms 21776 KB Output is correct
5 Correct 312 ms 21784 KB Output is correct
6 Correct 308 ms 21744 KB Output is correct
7 Correct 319 ms 20280 KB Output is correct
8 Correct 177 ms 21592 KB Output is correct
9 Correct 543 ms 30980 KB Output is correct
10 Correct 673 ms 31112 KB Output is correct
11 Correct 460 ms 30620 KB Output is correct
12 Correct 525 ms 26864 KB Output is correct
13 Correct 303 ms 35840 KB Output is correct
14 Correct 271 ms 23020 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 249 ms 24320 KB Output is correct
2 Correct 558 ms 26580 KB Output is correct
3 Correct 336 ms 33436 KB Output is correct
4 Correct 294 ms 26940 KB Output is correct
5 Correct 380 ms 28660 KB Output is correct
6 Correct 328 ms 28244 KB Output is correct
7 Correct 334 ms 25092 KB Output is correct
8 Correct 321 ms 33360 KB Output is correct
9 Correct 534 ms 30804 KB Output is correct
10 Correct 605 ms 30664 KB Output is correct
11 Correct 630 ms 30696 KB Output is correct
12 Correct 553 ms 26752 KB Output is correct
13 Correct 543 ms 38908 KB Output is correct
14 Correct 429 ms 22744 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 515 ms 31192 KB Output is correct
2 Correct 631 ms 27572 KB Output is correct
3 Correct 312 ms 38400 KB Output is correct
4 Correct 561 ms 31272 KB Output is correct
5 Correct 662 ms 31128 KB Output is correct
6 Correct 459 ms 30552 KB Output is correct
7 Correct 567 ms 27432 KB Output is correct
8 Correct 289 ms 38236 KB Output is correct
9 Correct 273 ms 22916 KB Output is correct