oj.uz

Submission #872751

# Submission time Handle Problem Language Result Execution time Memory
872751 2023-11-13T16:37:17 Z vjudge1 Ball Machine (BOI13_ballmachine) C++17
97.1429 / 100
 1000 ms 52972 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];
 
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 4 ms 24668 KB Output is correct
2 Correct 528 ms 38460 KB Output is correct
3 Correct 317 ms 34388 KB Output is correct
4 Correct 3 ms 24668 KB Output is correct
5 Correct 4 ms 24824 KB Output is correct
6 Correct 5 ms 24924 KB Output is correct
7 Correct 6 ms 24924 KB Output is correct
8 Correct 6 ms 24924 KB Output is correct
9 Correct 26 ms 27316 KB Output is correct
10 Correct 72 ms 30348 KB Output is correct
11 Correct 522 ms 38228 KB Output is correct
12 Correct 345 ms 34364 KB Output is correct
13 Correct 401 ms 36372 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 32540 KB Output is correct
2 Correct 724 ms 48100 KB Output is correct
3 Correct 287 ms 35676 KB Output is correct
4 Correct 320 ms 35504 KB Output is correct
5 Correct 382 ms 35672 KB Output is correct
6 Correct 350 ms 35168 KB Output is correct
7 Correct 329 ms 34396 KB Output is correct
8 Correct 192 ms 32468 KB Output is correct
9 Correct 598 ms 46272 KB Output is correct
10 Correct 693 ms 47960 KB Output is correct
11 Correct 494 ms 46172 KB Output is correct
12 Correct 694 ms 42788 KB Output is correct
13 Correct 292 ms 47408 KB Output is correct
14 Correct 290 ms 35640 KB Output is correct

Subtask #3
37.1428571429 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 252 ms 40756 KB Output is correct
2 Correct 726 ms 43552 KB Output is correct
3 Correct 391 ms 48724 KB Output is correct
4 Correct 408 ms 43100 KB Output is correct
5 Correct 412 ms 45136 KB Output is correct
6 Correct 455 ms 44412 KB Output is correct
7 Correct 459 ms 42076 KB Output is correct
8 Correct 409 ms 48656 KB Output is correct
9 Correct 732 ms 45980 KB Output is correct
10 Correct 947 ms 46988 KB Output is correct
11 Execution timed out 1002 ms 47000 KB Time limit exceeded
12 Correct 925 ms 42956 KB Output is correct
13 Correct 683 ms 52972 KB Output is correct
14 Correct 580 ms 39472 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 614 ms 46672 KB Output is correct
2 Correct 706 ms 43932 KB Output is correct
3 Correct 313 ms 50688 KB Output is correct
4 Correct 617 ms 46980 KB Output is correct
5 Correct 693 ms 45904 KB Output is correct
6 Correct 491 ms 45904 KB Output is correct
7 Correct 691 ms 43952 KB Output is correct
8 Correct 300 ms 51008 KB Output is correct
9 Correct 289 ms 35844 KB Output is correct