Submission #648424

#	Time	Username	Problem	Language	Result	Execution time	Memory
648424		ymm	Ball Machine (BOI13_ballmachine)	C++17	100 / 100	141 ms	22968 KiB

ballmachine

#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 / 25
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40
• Subtask 4: 5 / 5