oj.uz

Submission #872745

# Submission time Handle Problem Language Result Execution time Memory
872745 2023-11-13T16:30:30 Z vjudge1 Ball Machine (BOI13_ballmachine) C++17
97.1429 / 100
 1000 ms 39636 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) < v)
					l = mid;
				else
					r = mid;
			}
			cout << f[r] + 1 << '\n';
			add(r);
		}
		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
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 21336 KB Output is correct
2 Correct 952 ms 24868 KB Output is correct
3 Correct 416 ms 24796 KB Output is correct
4 Correct 3 ms 21336 KB Output is correct
5 Correct 4 ms 21340 KB Output is correct
6 Correct 4 ms 21340 KB Output is correct
7 Correct 5 ms 21340 KB Output is correct
8 Correct 5 ms 21340 KB Output is correct
9 Correct 43 ms 21764 KB Output is correct
10 Correct 64 ms 22352 KB Output is correct
11 Correct 895 ms 24704 KB Output is correct
12 Correct 434 ms 24852 KB Output is correct
13 Correct 857 ms 24432 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 24872 KB Output is correct
2 Correct 727 ms 33104 KB Output is correct
3 Correct 487 ms 25416 KB Output is correct
4 Correct 448 ms 24848 KB Output is correct
5 Correct 364 ms 25276 KB Output is correct
6 Correct 362 ms 24924 KB Output is correct
7 Correct 339 ms 23928 KB Output is correct
8 Correct 116 ms 24912 KB Output is correct
9 Correct 754 ms 32592 KB Output is correct
10 Correct 750 ms 33376 KB Output is correct
11 Correct 551 ms 32852 KB Output is correct
12 Correct 668 ms 29156 KB Output is correct
13 Correct 279 ms 37296 KB Output is correct
14 Correct 497 ms 25396 KB Output is correct

Subtask #3
37.1428571429 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 266 ms 27260 KB Output is correct
2 Correct 846 ms 29328 KB Output is correct
3 Correct 370 ms 35720 KB Output is correct
4 Correct 471 ms 30284 KB Output is correct
5 Correct 368 ms 30804 KB Output is correct
6 Correct 381 ms 31060 KB Output is correct
7 Correct 380 ms 27812 KB Output is correct
8 Correct 400 ms 35696 KB Output is correct
9 Correct 936 ms 32664 KB Output is correct
10 Correct 834 ms 33480 KB Output is correct
11 Correct 845 ms 33332 KB Output is correct
12 Correct 855 ms 29464 KB Output is correct
13 Correct 772 ms 39636 KB Output is correct
14 Execution timed out 1031 ms 25652 KB Time limit exceeded

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 740 ms 32720 KB Output is correct
2 Correct 756 ms 30148 KB Output is correct
3 Correct 257 ms 39032 KB Output is correct
4 Correct 690 ms 32548 KB Output is correct
5 Correct 791 ms 33348 KB Output is correct
6 Correct 566 ms 33436 KB Output is correct
7 Correct 751 ms 29264 KB Output is correct
8 Correct 276 ms 38996 KB Output is correct
9 Correct 498 ms 25588 KB Output is correct