oj.uz

Submission #872737

# Submission time Handle Problem Language Result Execution time Memory
872737 2023-11-13T16:12:21 Z vjudge1 Ball Machine (BOI13_ballmachine) C++17
83.6752 / 100
 1000 ms 40588 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 = 400;
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 5 ms 21596 KB Output is correct
2 Correct 901 ms 25444 KB Output is correct
3 Correct 467 ms 25552 KB Output is correct
4 Incorrect 3 ms 21340 KB Output isn't correct
5 Correct 4 ms 21596 KB Output is correct
6 Correct 5 ms 21592 KB Output is correct
7 Incorrect 7 ms 21596 KB Output isn't correct
8 Correct 9 ms 21596 KB Output is correct
9 Correct 27 ms 21872 KB Output is correct
10 Correct 149 ms 22360 KB Output is correct
11 Correct 957 ms 25432 KB Output is correct
12 Correct 459 ms 25500 KB Output is correct
13 Incorrect 866 ms 25424 KB Output isn't correct

Subtask #2
25.7142857143 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 180 ms 25424 KB Output is correct
2 Correct 773 ms 34208 KB Output is correct
3 Correct 386 ms 26576 KB Output is correct
4 Correct 533 ms 25328 KB Output is correct
5 Correct 441 ms 25820 KB Output is correct
6 Incorrect 443 ms 25568 KB Output isn't correct
7 Correct 331 ms 24304 KB Output is correct
8 Correct 178 ms 25428 KB Output is correct
9 Correct 834 ms 33180 KB Output is correct
10 Correct 777 ms 34132 KB Output is correct
11 Incorrect 639 ms 34272 KB Output isn't correct
12 Correct 651 ms 30308 KB Output is correct
13 Correct 301 ms 37912 KB Output is correct
14 Correct 375 ms 26832 KB Output is correct

Subtask #3
34.2857142857 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 315 ms 27476 KB Output is correct
2 Correct 901 ms 30620 KB Output is correct
3 Correct 363 ms 36460 KB Output is correct
4 Correct 408 ms 30804 KB Output is correct
5 Correct 377 ms 31696 KB Output is correct
6 Correct 376 ms 31568 KB Output is correct
7 Correct 364 ms 28752 KB Output is correct
8 Correct 351 ms 36432 KB Output is correct
9 Execution timed out 1052 ms 33312 KB Time limit exceeded
10 Correct 860 ms 34332 KB Output is correct
11 Correct 878 ms 34304 KB Output is correct
12 Correct 879 ms 30340 KB Output is correct
13 Correct 873 ms 40588 KB Output is correct
14 Execution timed out 1065 ms 26688 KB Time limit exceeded

Subtask #4
4.44444444444 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 847 ms 33556 KB Output is correct
2 Correct 796 ms 30504 KB Output is correct
3 Correct 330 ms 39840 KB Output is correct
4 Correct 794 ms 33492 KB Output is correct
5 Correct 751 ms 34296 KB Output is correct
6 Incorrect 667 ms 34232 KB Output isn't correct
7 Correct 824 ms 30548 KB Output is correct
8 Correct 343 ms 39764 KB Output is correct
9 Correct 652 ms 26348 KB Output is correct