Submission #298036

#	Time	Username	Problem	Language	Result	Execution time	Memory
298036		miss_robot	Ball Machine (BOI13_ballmachine)	C++14	100 / 100	370 ms	26344 KiB

ballmachine

#include <bits/stdc++.h>
 
#pragma GCC optimize("O3")
 
using namespace std;
 
const int N = 100000, L = 17;
int n, q, k, root, temp, c;
int p[L][N], mi[N], ball[N], lv[N], num[N];
vector<int> g[N];

bool comp(const int &a, const int &b){
	return mi[a] < mi[b];
}

void dfs(int u, int h){
	mi[u] = u;
	lv[u] = h++;
	for(int v : g[u]) dfs(v, h), mi[u] = min(mi[u], mi[v]);
	sort(g[u].begin(), g[u].end(), comp);
}

void traverse(int u){
	for(int v : g[u]) traverse(v);
	num[u] = c++;
}

int main(){
	cin.tie(0);
	ios::sync_with_stdio(0);
	cin >> n >> q;
	for(int i = 0, j; i < n; i++){
		cin >> j;
		if(!j) root = i, p[0][i] = i;
		else j--, p[0][i] = j, g[j].push_back(i);
	}
	dfs(root, 0);
	traverse(root);
	priority_queue< pair<int, int>, vector< pair<int, int> >, greater< pair<int, int> > > pq;
	for(int i = 0; i < n; i++) pq.push({num[i], i});
	for(int i = 1; i < L; i++)
		for(int j = 0; j < n; j++)
			p[i][j] = p[i-1][p[i-1][j]];
	while(q--){
		cin >> temp >> k;
		if(--temp){
			k--;
			temp = k;
			for(int i = L-1; i >= 0; i--)
				if(ball[p[i][k]]) k = p[i][k];
			ball[k] = 0;
			pq.push({num[k], k});
			cout << lv[temp] - lv[k] << "\n";
		}
		else{
			while(k--){
				if(!k) cout << pq.top().second+1 << "\n";
				ball[pq.top().second] = 1;
				pq.pop();
			}
		}
	}
}

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