oj.uz

Submission #872689

# Submission time Handle Problem Language Result Execution time Memory
872689 2023-11-13T14:58:19 Z vjudge1 Ball Machine (BOI13_ballmachine) C++17
89.3895 / 100
 683 ms 54100 KB 
#include<bits/stdc++.h>
using namespace std;
 
#define int long long
#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];
bool mrk[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) {
	mrk[id] = false;
	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];
		mrk[id * 2] = true;
	}
	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];
		mrk[id * 2 + 1] = true;
	}
}
 
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;
		mrk[id] = true;
		return;
	}
	if (r <= pl[id].F || l >= pl[id].S) 
		return;
	if (mrk[id])
		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;
	if (mrk[id])
		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[l] + 1 << '\n';
			add(0, l + 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
19.2307692308 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 25180 KB Output is correct
2 Correct 417 ms 35588 KB Output is correct
3 Correct 258 ms 33900 KB Output is correct
4 Incorrect 3 ms 25176 KB Output isn't correct
5 Correct 4 ms 25180 KB Output is correct
6 Correct 4 ms 25132 KB Output is correct
7 Incorrect 5 ms 25180 KB Output isn't correct
8 Correct 6 ms 25264 KB Output is correct
9 Correct 21 ms 25432 KB Output is correct
10 Correct 68 ms 27008 KB Output is correct
11 Correct 399 ms 35664 KB Output is correct
12 Correct 253 ms 34248 KB Output is correct
13 Incorrect 331 ms 34232 KB Output isn't correct

Subtask #2
25.7142857143 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 29164 KB Output is correct
2 Correct 582 ms 46372 KB Output is correct
3 Correct 244 ms 35384 KB Output is correct
4 Correct 266 ms 32548 KB Output is correct
5 Correct 287 ms 32696 KB Output is correct
6 Incorrect 285 ms 32072 KB Output isn't correct
7 Correct 279 ms 28964 KB Output is correct
8 Correct 138 ms 29264 KB Output is correct
9 Correct 488 ms 44940 KB Output is correct
10 Correct 597 ms 46416 KB Output is correct
11 Incorrect 428 ms 45900 KB Output isn't correct
12 Correct 561 ms 41188 KB Output is correct
13 Correct 239 ms 46780 KB Output is correct
14 Correct 240 ms 35376 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 219 ms 35664 KB Output is correct
2 Correct 673 ms 45140 KB Output is correct
3 Correct 317 ms 48248 KB Output is correct
4 Correct 316 ms 44268 KB Output is correct
5 Correct 359 ms 43536 KB Output is correct
6 Correct 393 ms 43672 KB Output is correct
7 Correct 387 ms 40276 KB Output is correct
8 Correct 340 ms 48648 KB Output is correct
9 Correct 581 ms 47696 KB Output is correct
10 Correct 610 ms 47780 KB Output is correct
11 Correct 637 ms 48828 KB Output is correct
12 Correct 683 ms 44676 KB Output is correct
13 Correct 569 ms 54100 KB Output is correct
14 Correct 494 ms 41076 KB Output is correct

Subtask #4
4.44444444444 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 518 ms 46628 KB Output is correct
2 Correct 596 ms 43020 KB Output is correct
3 Correct 242 ms 49236 KB Output is correct
4 Correct 509 ms 46816 KB Output is correct
5 Correct 583 ms 46228 KB Output is correct
6 Incorrect 417 ms 43592 KB Output isn't correct
7 Correct 608 ms 42964 KB Output is correct
8 Correct 235 ms 49280 KB Output is correct
9 Correct 246 ms 35284 KB Output is correct