oj.uz

Submission #648381

# Submission time Handle Problem Language Result Execution time Memory
648381 2022-10-06T09:42:14 Z ymm Ball Machine (BOI13_ballmachine) C++17
100 / 100
 157 ms 20768 KB 
#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 9292 KB Output is correct
3 Correct 50 ms 9548 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 2 ms 2772 KB Output is correct
9 Correct 7 ms 3092 KB Output is correct
10 Correct 15 ms 4472 KB Output is correct
11 Correct 64 ms 9248 KB Output is correct
12 Correct 51 ms 9468 KB Output is correct
13 Correct 69 ms 9264 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 6220 KB Output is correct
2 Correct 108 ms 16072 KB Output is correct
3 Correct 53 ms 12360 KB Output is correct
4 Correct 51 ms 6864 KB Output is correct
5 Correct 54 ms 6732 KB Output is correct
6 Correct 41 ms 6740 KB Output is correct
7 Correct 39 ms 6044 KB Output is correct
8 Correct 27 ms 6176 KB Output is correct
9 Correct 114 ms 16584 KB Output is correct
10 Correct 105 ms 16052 KB Output is correct
11 Correct 106 ms 16132 KB Output is correct
12 Correct 114 ms 14324 KB Output is correct
13 Correct 76 ms 18560 KB Output is correct
14 Correct 58 ms 12376 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 9668 KB Output is correct
2 Correct 125 ms 14656 KB Output is correct
3 Correct 106 ms 17100 KB Output is correct
4 Correct 71 ms 13900 KB Output is correct
5 Correct 74 ms 13480 KB Output is correct
6 Correct 85 ms 13600 KB Output is correct
7 Correct 93 ms 12272 KB Output is correct
8 Correct 104 ms 17100 KB Output is correct
9 Correct 101 ms 16712 KB Output is correct
10 Correct 129 ms 16384 KB Output is correct
11 Correct 129 ms 16328 KB Output is correct
12 Correct 134 ms 14724 KB Output is correct
13 Correct 130 ms 20768 KB Output is correct
14 Correct 79 ms 12372 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 16856 KB Output is correct
2 Correct 157 ms 14756 KB Output is correct
3 Correct 95 ms 20608 KB Output is correct
4 Correct 117 ms 16764 KB Output is correct
5 Correct 123 ms 16352 KB Output is correct
6 Correct 113 ms 16272 KB Output is correct
7 Correct 128 ms 14760 KB Output is correct
8 Correct 89 ms 20628 KB Output is correct
9 Correct 53 ms 12392 KB Output is correct