Submission #255587

#	Time	Username	Problem	Language	Result	Execution time	Memory
255587		Saboon	Ball Machine (BOI13_ballmachine)	C++14	100 / 100	743 ms	23800 KiB

ballmachine

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
const int maxn = 1e5 + 10;

vector<int> t[maxn];
int mnm[maxn], ft[maxn], pos[maxn], Time = 1;
int par[maxn][20];
int seg[4*maxn], lazy[4*maxn];

void shift(int,int,int);

int get(int id, int L, int R, int l, int r){
	if (r <= L or R <= l)
		return 0;
	if (l <= L and R <= r)
		return seg[id];
	shift(id,L,R);
	int mid = (L + R) >> 1;
	return get(2*id+0, L, mid, l, r) + get(2*id+1, mid, R, l, r);
}

void change(int id, int L, int R, int l, int r, int val){
	if (r <= L or R <= l)
		return;
	if (l <= L and R <= r){
		seg[id] = (R-L) * val;
		lazy[id] = val;
		return;
	}
	int mid = (L + R) >> 1;
	shift(id,L,R);
	change(2*id+0, L, mid, l, r, val);
	change(2*id+1, mid, R, l, r, val);
	seg[id] = seg[2*id+0] + seg[2*id+1];
}

void shift(int id, int L, int R){
	if (lazy[id] == -1)
		return;
	int mid = (L + R) >> 1;
	change(2*id+0, L, mid, L, mid, lazy[id]);
	change(2*id+1, mid, R, mid, R, lazy[id]);
	lazy[id] = -1;
}

void dfs(int v){
	for (auto u : t[v])
		dfs(u);
	ft[v] = Time;
	pos[Time++] = v;
}

int dfsinit(int v){
	mnm[v] = v;
	for (auto u : t[v])
		mnm[v] = min(mnm[v], dfsinit(u));
	sort(t[v].begin(), t[v].end(), [](int x, int y){ return mnm[x] < mnm[y]; });
	return mnm[v];
}

int main(){
	ios_base::sync_with_stdio(false);
	int n, q;
	cin >> n >> q;
	int root = -1;
	memset(par, -1, sizeof par);
	for (int i = 1; i <= n; i++){
		int p;
		cin >> p;
		if (p == 0)
			root = i;
		else{
			t[p].push_back(i);
			par[i][0] = p;
		}
	}
	for (int i = 1; i <= 17; i++)
		for (int v = 1; v <= n; v++)
			if (par[v][i-1] != -1)
				par[v][i] = par[par[v][i-1]][i-1];
	dfsinit(root);
	dfs(root);
	memset(lazy, -1, sizeof lazy);
	while (q --){
		int type, x;
		cin >> type >> x;
		if (type == 1){
			int lo = 0, hi = n+1;
			while (hi - lo > 1){
				int mid = (lo + hi) >> 1;
				if (mid - get(1,1,n+1,1,mid+1) >= x)
					hi = mid;
				else
					lo = mid;
			}
			change(1,1,n+1,1,hi+1,1);
			cout << pos[hi] << '\n';
		}
		else{
			int ans = 0;
			for (int i = 17; i >= 0; i--)
				if (par[x][i] != -1 and get(1,1,n+1,ft[par[x][i]],ft[par[x][i]]+1) == 1)
					x = par[x][i], ans += (1 << i);
			cout << ans << '\n';
			change(1,1,n+1,ft[x],ft[x]+1,0);
		}
	}
}

• Subtask 1: 25 / 25
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40
• Subtask 4: 5 / 5