Submission #872602

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
872602	2023-11-13T12:37:05 Z	vjudge1	Ball Machine (BOI13_ballmachine)	C++17	89.3895 / 100	847 ms	54752 KB

ballmachine

#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[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	4 ms	24668 KB	Output is correct
2	Correct	489 ms	39400 KB	Output is correct
3	Correct	359 ms	35664 KB	Output is correct
4	Incorrect	4 ms	24664 KB	Output isn't correct
5	Correct	4 ms	24668 KB	Output is correct
6	Correct	5 ms	24924 KB	Output is correct
7	Incorrect	6 ms	24924 KB	Output isn't correct
8	Correct	6 ms	24924 KB	Output is correct
9	Correct	27 ms	27408 KB	Output is correct
10	Correct	74 ms	30300 KB	Output is correct
11	Correct	502 ms	39508 KB	Output is correct
12	Correct	329 ms	35408 KB	Output is correct
13	Incorrect	438 ms	37520 KB	Output isn't correct

Subtask #2

25.7142857143 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	184 ms	32956 KB	Output is correct
2	Correct	698 ms	49224 KB	Output is correct
3	Correct	306 ms	36612 KB	Output is correct
4	Correct	306 ms	36180 KB	Output is correct
5	Correct	338 ms	36420 KB	Output is correct
6	Incorrect	344 ms	35856 KB	Output isn't correct
7	Correct	350 ms	34960 KB	Output is correct
8	Correct	193 ms	33256 KB	Output is correct
9	Correct	642 ms	47616 KB	Output is correct
10	Correct	753 ms	49232 KB	Output is correct
11	Incorrect	507 ms	47304 KB	Output isn't correct
12	Correct	688 ms	44340 KB	Output is correct
13	Correct	300 ms	48532 KB	Output is correct
14	Correct	294 ms	37460 KB	Output is correct

Subtask #3

40.0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	267 ms	41592 KB	Output is correct
2	Correct	740 ms	44412 KB	Output is correct
3	Correct	399 ms	51192 KB	Output is correct
4	Correct	414 ms	43780 KB	Output is correct
5	Correct	456 ms	44820 KB	Output is correct
6	Correct	448 ms	45336 KB	Output is correct
7	Correct	455 ms	42880 KB	Output is correct
8	Correct	387 ms	50924 KB	Output is correct
9	Correct	672 ms	47720 KB	Output is correct
10	Correct	730 ms	48520 KB	Output is correct
11	Correct	847 ms	48212 KB	Output is correct
12	Correct	724 ms	44624 KB	Output is correct
13	Correct	683 ms	54752 KB	Output is correct
14	Correct	595 ms	40768 KB	Output is correct

Subtask #4

4.44444444444 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	623 ms	47872 KB	Output is correct
2	Correct	689 ms	43984 KB	Output is correct
3	Correct	319 ms	52052 KB	Output is correct
4	Correct	620 ms	47696 KB	Output is correct
5	Correct	730 ms	47188 KB	Output is correct
6	Incorrect	510 ms	47172 KB	Output isn't correct
7	Correct	731 ms	43984 KB	Output is correct
8	Correct	327 ms	51800 KB	Output is correct
9	Correct	300 ms	36696 KB	Output is correct