제출 #1296256

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1296256		Jawad_Akbar_JJ	Ball Machine (BOI13_ballmachine)	C++20	100 / 100	133 ms	30180 KiB

ballmachine

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;
const int N = 1<<17;
vector<int> nei[N];
int st[N], ch[N], Par[N][20], Mn[N], ft[N], ord[N], c1, c2;

void dfs2(int u){
	vector<pair<int,int>> nb;
	for (int i : nei[u])
		nb.push_back({Mn[i], i});

	sort(nb.begin(), nb.end());
	for (auto [mn, i] : nb)
		dfs2(i);

	ord[u] = ++c1;
}

void dfs1(int u, int p){
	ch[u] = 1, st[u] = ++c2, Mn[u] = u;
	Par[u][0] = p;
	for (int i=0;i<17;i++)
		Par[u][i+1] = Par[Par[u][i]][i];

	for (int i : nei[u]){
		dfs1(i, u);
		Mn[u] = min(Mn[u], Mn[i]);
		ch[u] += ch[i];
	}
}

void Add(int i, int v){
	for (; i < N; i += i & -i)
		ft[i] += v;
}

int get(int i, int ans = 0){
	for (; i; i -= i & -i)
		ans += ft[i];
	return ans;
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int n, p, q;
	cin>>n>>q;

	for (int i=1;i<=n;i++){
		cin>>p;
		nei[p].push_back(i);
	}
	dfs1(nei[0][0], 0);
	dfs2(nei[0][0]);

	set<pair<int,int>> stt;
	for (int i=1;i<=n;i++)
		stt.insert({ord[i], i});
	
	for (int i=1;i<=q;i++){
		int t, u, v;
		cin>>t>>v;

		if (t == 2){
			int up = get(st[v]) - 1;
			for (int i=0;i<=17;i++){
				if ((1<<i) & up)
					v = Par[v][i];
			}
			cout<<up<<'\n';
			Add(st[v], -1); Add(st[v] + ch[v], 1);
			stt.insert({ord[v], v});
			continue;
		}

		while (v--){
			u = (*stt.begin()).second;
			stt.erase(begin(stt));
			Add(st[u], 1); Add(st[u] + ch[u], -1);
		}

		cout<<u<<'\n';
	}

}

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