oj.uz

Submission #870231

# Submission time Handle Problem Language Result Execution time Memory
870231 2023-11-07T09:12:11 Z vjudge1 Ball Machine (BOI13_ballmachine) C++17
89.3895 / 100
 715 ms 76200 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 = 2e5 + 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);
	return ask(l, r, id * 2) + ask(l, r, id * 2 + 1);
}

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 7 ms 45148 KB Output is correct
2 Correct 426 ms 56816 KB Output is correct
3 Correct 287 ms 53072 KB Output is correct
4 Incorrect 6 ms 45400 KB Output isn't correct
5 Correct 6 ms 45432 KB Output is correct
6 Correct 7 ms 45148 KB Output is correct
7 Incorrect 8 ms 45156 KB Output isn't correct
8 Correct 9 ms 45192 KB Output is correct
9 Correct 26 ms 47728 KB Output is correct
10 Correct 67 ms 48712 KB Output is correct
11 Correct 442 ms 56400 KB Output is correct
12 Correct 281 ms 53456 KB Output is correct
13 Incorrect 335 ms 55224 KB Output isn't correct

Subtask #2
25.7142857143 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 50772 KB Output is correct
2 Correct 631 ms 68436 KB Output is correct
3 Correct 244 ms 56384 KB Output is correct
4 Correct 265 ms 53840 KB Output is correct
5 Correct 322 ms 54108 KB Output is correct
6 Incorrect 334 ms 51300 KB Output isn't correct
7 Correct 291 ms 52524 KB Output is correct
8 Correct 166 ms 50772 KB Output is correct
9 Correct 521 ms 67360 KB Output is correct
10 Correct 627 ms 68432 KB Output is correct
11 Incorrect 442 ms 66228 KB Output isn't correct
12 Correct 582 ms 63572 KB Output is correct
13 Correct 257 ms 67904 KB Output is correct
14 Correct 248 ms 56292 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 249 ms 60000 KB Output is correct
2 Correct 635 ms 66128 KB Output is correct
3 Correct 405 ms 71368 KB Output is correct
4 Correct 323 ms 65880 KB Output is correct
5 Correct 431 ms 66360 KB Output is correct
6 Correct 427 ms 66524 KB Output is correct
7 Correct 361 ms 63220 KB Output is correct
8 Correct 349 ms 71508 KB Output is correct
9 Correct 551 ms 69312 KB Output is correct
10 Correct 701 ms 70000 KB Output is correct
11 Correct 693 ms 70060 KB Output is correct
12 Correct 715 ms 66668 KB Output is correct
13 Correct 619 ms 76200 KB Output is correct
14 Correct 530 ms 62424 KB Output is correct

Subtask #4
4.44444444444 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 559 ms 67728 KB Output is correct
2 Correct 666 ms 65452 KB Output is correct
3 Correct 271 ms 69896 KB Output is correct
4 Correct 570 ms 67620 KB Output is correct
5 Correct 664 ms 68268 KB Output is correct
6 Incorrect 431 ms 66028 KB Output isn't correct
7 Correct 637 ms 64976 KB Output is correct
8 Correct 265 ms 70056 KB Output is correct
9 Correct 239 ms 56120 KB Output is correct