oj.uz

Submission #872738

# Submission time Handle Problem Language Result Execution time Memory
872738 2023-11-13T16:15:01 Z vjudge1 Ball Machine (BOI13_ballmachine) C++17
89.3895 / 100
 987 ms 39452 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, SQ = 320;
vector<int> g[N];
int n, q, t, f[N], p[N], par[M][N], root, d[N], h[N], sum[SQ];
bool dp[SQ], a[SQ * SQ + 12];

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 add(int x) {
	for (int i = 0; (i + 1) * SQ - 1 < x; i++) {
		sum[i] = SQ;
		dp[i] = true;
	}
	if (!dp[x / SQ]) 
		for (int i = (x / SQ) * SQ; i <= x; i++)
			if (!a[i]) {
				a[i] = true;
				sum[x / SQ]++;
			}
}

void rem(int x) {
	if (dp[x / SQ]) {
		fill(a + x - x % SQ, a + x - x % SQ + SQ, 1);
		sum[x / SQ] = SQ - 1;
		dp[x / SQ] = false;
		a[x] = false;
	}
	else if (a[x]) {
		a[x] = false;
		sum[x / SQ]--;
	}
}

int ask(int x) {
	int res = 0;
	for (int i = 0; (i + 1) * SQ - 1 < x; i++)
		res += sum[i];
	if (dp[x / SQ]) 
		res += (x % SQ) + 1;
	else 
		for (int i = x - x % SQ; i <= x; i++)
			res += a[i];
	return res;
}
 
void query() {
	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(mid + 1) <= v)
					l = mid;
				else
					r = mid;
			}
			cout << f[l] + 1 << '\n';
			add(l);
		}
		else {
			v--;
			int z = v;
			for (int i = M - 1; ~i; i--)
				if ((ask(p[par[i][v]]) - ask(p[par[i][v]] - 1)) > 0)
					v = par[i][v];
			cout << h[z] - h[v] << '\n';
			rem(p[v]);
		}
	}
}
 
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 21340 KB Output is correct
2 Correct 874 ms 24696 KB Output is correct
3 Correct 421 ms 24656 KB Output is correct
4 Incorrect 3 ms 21336 KB Output isn't correct
5 Correct 4 ms 21592 KB Output is correct
6 Correct 4 ms 21340 KB Output is correct
7 Incorrect 5 ms 21340 KB Output isn't correct
8 Correct 5 ms 21340 KB Output is correct
9 Correct 43 ms 21596 KB Output is correct
10 Correct 62 ms 22348 KB Output is correct
11 Correct 839 ms 24660 KB Output is correct
12 Correct 416 ms 24876 KB Output is correct
13 Incorrect 805 ms 24572 KB Output isn't correct

Subtask #2
25.7142857143 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 24892 KB Output is correct
2 Correct 712 ms 33112 KB Output is correct
3 Correct 464 ms 25836 KB Output is correct
4 Correct 441 ms 24912 KB Output is correct
5 Correct 366 ms 24920 KB Output is correct
6 Incorrect 347 ms 25092 KB Output isn't correct
7 Correct 337 ms 23840 KB Output is correct
8 Correct 116 ms 24916 KB Output is correct
9 Correct 739 ms 32256 KB Output is correct
10 Correct 689 ms 33104 KB Output is correct
11 Incorrect 537 ms 33004 KB Output isn't correct
12 Correct 657 ms 29412 KB Output is correct
13 Correct 273 ms 37264 KB Output is correct
14 Correct 465 ms 25412 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 268 ms 27028 KB Output is correct
2 Correct 782 ms 29288 KB Output is correct
3 Correct 350 ms 35668 KB Output is correct
4 Correct 408 ms 30292 KB Output is correct
5 Correct 391 ms 30864 KB Output is correct
6 Correct 385 ms 31068 KB Output is correct
7 Correct 357 ms 27808 KB Output is correct
8 Correct 370 ms 35724 KB Output is correct
9 Correct 893 ms 32748 KB Output is correct
10 Correct 774 ms 33156 KB Output is correct
11 Correct 775 ms 33360 KB Output is correct
12 Correct 819 ms 29420 KB Output is correct
13 Correct 722 ms 39452 KB Output is correct
14 Correct 987 ms 25648 KB Output is correct

Subtask #4
4.44444444444 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 672 ms 32596 KB Output is correct
2 Correct 739 ms 29316 KB Output is correct
3 Correct 270 ms 39304 KB Output is correct
4 Correct 664 ms 32376 KB Output is correct
5 Correct 654 ms 33104 KB Output is correct
6 Incorrect 553 ms 33104 KB Output isn't correct
7 Correct 721 ms 29524 KB Output is correct
8 Correct 262 ms 39108 KB Output is correct
9 Correct 476 ms 25688 KB Output is correct