제출 #1181041

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1181041		kadir	Ball Machine (BOI13_ballmachine)	C++20	100 / 100	110 ms	41692 KiB

ballmachine

#include<bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define pb push_back
using namespace std;
const ll mod=1e9+7;
const ll inf=1e18;
const ll mxn=1e5+5;
const ll MAX=1e9+6;
const ll logk=18;
vector<ll> adj[mxn],pos(mxn);
set<pair<ll,ll>> s;
ll dp[mxn][logk];
ll mn[mxn],t=0;
bool vis[mxn];
vector<ll> v;
void dfs(ll x) {
    mn[x]=x;
    for(auto u:adj[x]) {
        dfs(u);
        mn[x]=min(mn[u],mn[x]);
    }
}
void dfs2(ll x) {
    vector<pair<ll,ll>> p;
    for(auto u:adj[x]) {
        p.pb({mn[u],u});
    }
    sort(p.begin(),p.end());
    for(auto [val,u]:p) {
        dfs2(u);
    }
    v.pb(x);
    s.insert({t,x});
    pos[x]=t;
    t++;
}
ll op1() {
    pair<ll,ll> x=*s.begin();
    vis[x.ss]=true;
    s.erase(x);
    return x.ss;
}
ll op2(ll x) {
	ll ans=0;
	for(ll i=16; i>=0; i--) {
		if(dp[x][i]>-1&&vis[dp[x][i]]){
		    ans+=(1<<i);
		    x=dp[x][i];
		    }
		}
	vis[x]=false;
	s.insert({pos[x],x});
	return ans;
}
int main(){
    ios_base::sync_with_stdio(false); 
	cin.tie(0); 
	cout.tie(0);
	ll n,q,d;
    cin>>n>>q;
    for(ll i=1; i<=n; i++) {
        ll p;
        cin>>p;
        if(p>0) {
            adj[p-1].pb(i-1);
        }
        else {
            d=i-1;
        }
    }
    dfs(d);
    dfs2(d);
    for(ll i=0; i<n; i++) {
        for(ll j=0; j<logk; j++) {
            dp[i][j]=-1;
        }
    }
    for(ll i=0; i<n; i++) {
        for(auto x:adj[i]) {
            dp[x][0]=i;
        }
    }
    for(ll j=1; j<logk; j++) {
        for(ll i=0; i<n; i++) { 
            if(dp[i][j-1]>-1&&dp[dp[i][j-1]][j-1]>-1) {
                dp[i][j]=dp[dp[i][j-1]][j-1];
            }
        }
    }
    while(q--) {
        ll t;
        cin>>t;
        if(t==1) {
            ll k;
            cin>>k;
            for(ll i=1; i<k; i++) {
                op1();
			}
            cout<<op1()+1<<"\n";
        } else {
            ll x;
            cin>>x;
            x--;
            cout<<op2(x)<<"\n";
        }
    }
}    

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