제출 #1292136

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1292136		elotelo966	Ball Machine (BOI13_ballmachine)	C++20	100 / 100	169 ms	55120 KiB

ballmachine

#include <bits/stdc++.h>
using namespace std;
 
#define int long long
#define OYY LLONG_MAX
#define mod 1000000007
#define faster ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define FOR for(int i=1;i<=n;i++)
#define mid (start+end)/2
#define lim 100005
#define fi first
#define se second
#define pb push_back

typedef long double lo;

int n,q,l;

int root;

vector<int> v[lim];

int mini[lim],mp[lim],col[lim],depth[lim];

vector<int> sira;

int up[lim][35];

inline void dfs(int node,int ata){
	up[node][0]=ata;
	mini[node]=node;
	depth[node]=depth[ata]+1;
	for(int i=1;i<=l;i++){
		up[node][i]=up[up[node][i-1]][i-1];
	}
	for(auto go:v[node]){
		if(go==ata)continue;
		dfs(go,node);
		mini[node]=min(mini[node],mini[go]);
	}
}

inline void dfs2(int node,int ata){
	vector<pair<int,int>> cur_sira;
	for(auto go:v[node]){
		if(go==ata)continue;
		cur_sira.pb({mini[go],go});
	}
	
	sort(cur_sira.begin(),cur_sira.end());
	
	for(auto a:cur_sira){
		dfs2(a.se,node);
	}
	
	sira.pb(node);
}

inline int cal(int node){
	for(int i=l;i>=0;i--){
		if(col[up[node][i]]){
			node=up[node][i];
		}
	}
	return node;
}

int32_t main(){
	faster
	cin>>n>>q;
	
	l=ceil(log2(n));
	
	FOR{
		int x;cin>>x;
		if(x==0)root=i;
		else{
			v[i].pb(x);
			v[x].pb(i);
		}
	}
		
	dfs(root,root);
	
	dfs2(root,-1);
		
	//~ for(auto a:sira){
		//~ cout<<a<<" ";
	//~ }
	
	set<pair<int,int>> bos;
	
	for(int i=0;i<n;i++){
		bos.insert({i,sira[i]});
		mp[sira[i]]=i;
	}
	
	while(q--){
		int ty,k;cin>>ty>>k;
		int cev;
		if(ty==1){
			while(k--){
				auto tut=*bos.begin();
				int bas=tut.se;
				col[bas]=1;
				bos.erase(tut);
				cev=bas;
			}
		}
		else{
			int cur=cal(k);
			col[cur]=0;
			bos.insert({mp[cur],cur});
			cev=depth[k]-depth[cur];
		}
		
		cout<<cev<<'\n';
		
	}
	
	return 0;
}

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