oj.uz

Submission #870233

# Submission time Handle Problem Language Result Execution time Memory
870233 2023-11-07T09:14:54 Z vjudge1 Ball Machine (BOI13_ballmachine) C++17
89.3895 / 100
 728 ms 76128 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 + 1};
	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 45144 KB Output is correct
2 Correct 398 ms 56764 KB Output is correct
3 Correct 218 ms 53076 KB Output is correct
4 Incorrect 6 ms 45148 KB Output isn't correct
5 Correct 6 ms 45148 KB Output is correct
6 Correct 7 ms 45148 KB Output is correct
7 Incorrect 8 ms 45144 KB Output isn't correct
8 Correct 8 ms 45232 KB Output is correct
9 Correct 26 ms 47688 KB Output is correct
10 Correct 69 ms 48724 KB Output is correct
11 Correct 395 ms 56628 KB Output is correct
12 Correct 225 ms 53596 KB Output is correct
13 Incorrect 342 ms 55104 KB Output isn't correct

Subtask #2
25.7142857143 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 50772 KB Output is correct
2 Correct 634 ms 68432 KB Output is correct
3 Correct 251 ms 56508 KB Output is correct
4 Correct 282 ms 53912 KB Output is correct
5 Correct 303 ms 54100 KB Output is correct
6 Incorrect 304 ms 51540 KB Output isn't correct
7 Correct 302 ms 52564 KB Output is correct
8 Correct 150 ms 50768 KB Output is correct
9 Correct 520 ms 67152 KB Output is correct
10 Correct 629 ms 68420 KB Output is correct
11 Incorrect 436 ms 66236 KB Output isn't correct
12 Correct 570 ms 63652 KB Output is correct
13 Correct 247 ms 67784 KB Output is correct
14 Correct 236 ms 56124 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 220 ms 59216 KB Output is correct
2 Correct 728 ms 66076 KB Output is correct
3 Correct 339 ms 71276 KB Output is correct
4 Correct 317 ms 65876 KB Output is correct
5 Correct 375 ms 66536 KB Output is correct
6 Correct 407 ms 66388 KB Output is correct
7 Correct 403 ms 63416 KB Output is correct
8 Correct 336 ms 71252 KB Output is correct
9 Correct 601 ms 69072 KB Output is correct
10 Correct 698 ms 70484 KB Output is correct
11 Correct 672 ms 70316 KB Output is correct
12 Correct 632 ms 66112 KB Output is correct
13 Correct 571 ms 76128 KB Output is correct
14 Correct 507 ms 62772 KB Output is correct

Subtask #4
4.44444444444 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 535 ms 67600 KB Output is correct
2 Correct 606 ms 65068 KB Output is correct
3 Correct 271 ms 69876 KB Output is correct
4 Correct 522 ms 67540 KB Output is correct
5 Correct 632 ms 68416 KB Output is correct
6 Incorrect 470 ms 66248 KB Output isn't correct
7 Correct 647 ms 65072 KB Output is correct
8 Correct 258 ms 69788 KB Output is correct
9 Correct 241 ms 56172 KB Output is correct