Submission #833639

#	Time	Username	Problem	Language	Result	Execution time	Memory
833639		yusuf12360	Ball Machine (BOI13_ballmachine)	C++14	100 / 100	179 ms	36844 KiB

ballmachine

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n, q, timer;
vector<int> ord, mn, stat, h;
vector<vector<int>> par;
vector<vector<pair<int, int>>> adj;
void dfs1(int u=0, int H=0) {
	mn[u]=u; h[u]=H;
	for(auto &p : adj[u])
		dfs1(p.second, H+1), mn[u]=min(mn[u], p.first=mn[p.second]);
}
void dfs2(int u=0) {
	for(auto p : adj[u])
		dfs2(p.second);
	ord[u]=timer--;
}
signed main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> q;
	ord.resize(n+1); adj.resize(n+1);
	par.resize(n+1, vector<int>(20));
	mn.resize(n+1); stat.resize(n+1);
	h.resize(n+1);
	for(int i=1; i<=n; i++) {
		int p; cin >> p;
		adj[p].push_back({i, i});
		par[i][0]=p;
	}
	for(int d=1; d<20; d++)
		for(int i=0; i<=n; i++) par[i][d]=par[par[i][d-1]][d-1];
	dfs1();
	for(auto &p : adj) sort(p.begin(), p.end());
	dfs2();
	priority_queue<pair<int, int>> pq;
	for(int i=0; i<=n; i++) pq.push({ord[i], i});
	while(q--) {
		int type, in; cin >> type >> in;
		if(type==1) {
			int las;
			while(in--) 
				stat[las=pq.top().second]=1, pq.pop();
			cout << las << '\n';
		} else {
			int prev; prev=h[in];
			for(int d=19; d>=0; d--) if(stat[par[in][d]]) in=par[in][d];
			stat[in]=0; pq.push({ord[in], in});
			cout << prev-h[in] << '\n';
		}
	}
	return 0;
}

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