oj.uz

Submission #648424

# Submission time Handle Problem Language Result Execution time Memory
648424 2022-10-06T11:39:26 Z ymm Ball Machine (BOI13_ballmachine) C++17
100 / 100
 141 ms 22968 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx")

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;
 
const int N = 100'032;
const int lg = 17;
vector<int> A[N];
bitset<N> is_free;
int anc[N][lg];
int dfs_time[N], inv_dfs_time[N];
int height[N];
int rt;
int smallest[N];
 
int dfs1(int v)
{
	smallest[v] = v;
	for (int u : A[v])
		smallest[v] = min(smallest[v], dfs1(u));
	return smallest[v];
}
 
void dfs2(int v, int p, int h, int &t)
{
	height[v] = h;
	anc[v][0] = p;
	Loop (i,0,lg-1)
		anc[v][i+1] = anc[anc[v][i]][i];
	for (int u : A[v])
		dfs2(u, v, h+1, t);
	dfs_time[v] = t;
	inv_dfs_time[t] = v;
	++t;
}
 
int add(int cnt)
{
	int lst = -1;
	while (cnt--) {
		lst = is_free._Find_next(lst);
		is_free[lst] = 0;
	}
	return inv_dfs_time[lst];
}
 
int rem(int v)
{
	int u = v;
	LoopR (i,0,lg) {
		if (!is_free[dfs_time[anc[u][i]]])
			u = anc[u][i];
	}
	is_free[dfs_time[u]] = 1;
	return height[v] - height[u];
 
}
 
int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	int n, q;
	cin >> n >> q;
	Loop (i,0,n) {
		int p;
		cin >> p;
		if (p)
			A[p-1].push_back(i);
		else
			rt = i;
	}
	dfs1(rt);
	Loop (i,0,n) {
		sort(A[i].begin(), A[i].end(), [&](int v, int u) {
			return smallest[v] < smallest[u];
		});
	}
	dfs2(rt, rt, 0, *new int(0));
	is_free.set();
	while (q--) {
		int t, x;
		cin >> t >> x;
		if (t == 1)
			cout << add(x)+1 << '\n';
		else
			cout << rem(x-1) << '\n';
	}
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 67 ms 9792 KB Output is correct
3 Correct 50 ms 9980 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2772 KB Output is correct
7 Correct 2 ms 2772 KB Output is correct
8 Correct 3 ms 2772 KB Output is correct
9 Correct 5 ms 3076 KB Output is correct
10 Correct 13 ms 4568 KB Output is correct
11 Correct 68 ms 9772 KB Output is correct
12 Correct 48 ms 9984 KB Output is correct
13 Correct 66 ms 9720 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 6916 KB Output is correct
2 Correct 100 ms 17368 KB Output is correct
3 Correct 62 ms 12952 KB Output is correct
4 Correct 46 ms 7672 KB Output is correct
5 Correct 46 ms 7544 KB Output is correct
6 Correct 44 ms 7552 KB Output is correct
7 Correct 46 ms 6608 KB Output is correct
8 Correct 28 ms 6952 KB Output is correct
9 Correct 95 ms 17904 KB Output is correct
10 Correct 112 ms 17508 KB Output is correct
11 Correct 111 ms 17388 KB Output is correct
12 Correct 106 ms 15156 KB Output is correct
13 Correct 80 ms 20428 KB Output is correct
14 Correct 60 ms 12912 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 10616 KB Output is correct
2 Correct 119 ms 15560 KB Output is correct
3 Correct 96 ms 18860 KB Output is correct
4 Correct 79 ms 15056 KB Output is correct
5 Correct 87 ms 14604 KB Output is correct
6 Correct 84 ms 14644 KB Output is correct
7 Correct 66 ms 13052 KB Output is correct
8 Correct 93 ms 18896 KB Output is correct
9 Correct 120 ms 17936 KB Output is correct
10 Correct 115 ms 17560 KB Output is correct
11 Correct 113 ms 17624 KB Output is correct
12 Correct 130 ms 15624 KB Output is correct
13 Correct 141 ms 22968 KB Output is correct
14 Correct 86 ms 12984 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 18084 KB Output is correct
2 Correct 103 ms 15540 KB Output is correct
3 Correct 92 ms 22748 KB Output is correct
4 Correct 111 ms 18216 KB Output is correct
5 Correct 115 ms 17612 KB Output is correct
6 Correct 102 ms 17484 KB Output is correct
7 Correct 117 ms 15660 KB Output is correct
8 Correct 82 ms 22732 KB Output is correct
9 Correct 56 ms 13020 KB Output is correct