oj.uz

Submission #870230

# Submission time Handle Problem Language Result Execution time Memory
870230 2023-11-07T09:08:21 Z vjudge1 Ball Machine (BOI13_ballmachine) C++17
89.3895 / 100
 701 ms 76064 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 = 0, 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 res = 0, z = v;
			for (int i = M - 1; ~i; i--)
				if (ask(p[par[i][v]], p[par[i][v]] + 1))
					v = par[i][v], res += (1 << i);
			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 433 ms 56824 KB Output is correct
3 Correct 254 ms 53076 KB Output is correct
4 Incorrect 6 ms 45144 KB Output isn't correct
5 Correct 6 ms 45148 KB Output is correct
6 Correct 8 ms 45144 KB Output is correct
7 Incorrect 9 ms 45144 KB Output isn't correct
8 Correct 9 ms 45148 KB Output is correct
9 Correct 26 ms 47732 KB Output is correct
10 Correct 71 ms 48716 KB Output is correct
11 Correct 462 ms 56724 KB Output is correct
12 Correct 257 ms 53032 KB Output is correct
13 Incorrect 343 ms 55124 KB Output isn't correct

Subtask #2
25.7142857143 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 50736 KB Output is correct
2 Correct 604 ms 68576 KB Output is correct
3 Correct 283 ms 56128 KB Output is correct
4 Correct 290 ms 53852 KB Output is correct
5 Correct 338 ms 54012 KB Output is correct
6 Incorrect 305 ms 51280 KB Output isn't correct
7 Correct 284 ms 52468 KB Output is correct
8 Correct 186 ms 50772 KB Output is correct
9 Correct 547 ms 67496 KB Output is correct
10 Correct 635 ms 68560 KB Output is correct
11 Incorrect 415 ms 65900 KB Output isn't correct
12 Correct 603 ms 63792 KB Output is correct
13 Correct 313 ms 67680 KB Output is correct
14 Correct 276 ms 56128 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 247 ms 59216 KB Output is correct
2 Correct 690 ms 66128 KB Output is correct
3 Correct 363 ms 71604 KB Output is correct
4 Correct 310 ms 65868 KB Output is correct
5 Correct 380 ms 66520 KB Output is correct
6 Correct 420 ms 66536 KB Output is correct
7 Correct 395 ms 63636 KB Output is correct
8 Correct 318 ms 71212 KB Output is correct
9 Correct 585 ms 69376 KB Output is correct
10 Correct 645 ms 70208 KB Output is correct
11 Correct 701 ms 70460 KB Output is correct
12 Correct 617 ms 66128 KB Output is correct
13 Correct 578 ms 76064 KB Output is correct
14 Correct 538 ms 62880 KB Output is correct

Subtask #4
4.44444444444 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 508 ms 67384 KB Output is correct
2 Correct 650 ms 64936 KB Output is correct
3 Correct 319 ms 69832 KB Output is correct
4 Correct 555 ms 67408 KB Output is correct
5 Correct 623 ms 68452 KB Output is correct
6 Incorrect 440 ms 66340 KB Output isn't correct
7 Correct 627 ms 64976 KB Output is correct
8 Correct 301 ms 69788 KB Output is correct
9 Correct 277 ms 56120 KB Output is correct