Submission #742262

#	Time	Username	Problem	Language	Result	Execution time	Memory
742262		irmuun	Ball Machine (BOI13_ballmachine)	C++17	100 / 100	380 ms	31496 KiB

ballmachine

#include<bits/stdc++.h>
 
using namespace std;
 
#define pb push_back
#define ll long long
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
 
const ll N=1e5+5,log_n=17;
vector<int>adj[N],pos(N);
int n,q,root,used[N],mn[N],cur=0;
int up[N][log_n];
set<pair<int,int>>s;
vector<int>ord;
void cal(int v){
    mn[v]=v;
    for(auto u:adj[v]){
        cal(u);
        mn[v]=min(mn[u],mn[v]);
    }
}
void dfs(int v){
    vector<pair<int,int>>p;
    for(auto u:adj[v]){
        p.pb({mn[u],u});
    }
    sort(all(p));
    for(auto [val,u]:p){
        dfs(u);
    }
    ord.pb(v);
    s.insert({cur,v});
    pos[v]=cur;
    cur++;
}
int op1(){
    pair<int,int>x=*s.begin();
    used[x.ss]=1;
    s.erase(x);
    return x.ss;
}
int op2(int v){
    int x=v;
    int ans=0;
    for(int i=16;i>=0;i--){
        if(up[x][i]>-1&&used[up[x][i]]==1){
            ans+=(1<<i);
            x=up[x][i];
        }
    }
    used[x]=0;
    s.insert({pos[x],x});
    return ans;
}
 
int main(){
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        int p;
        cin>>p;
        if(p>0){
            adj[p-1].pb(i-1);
        }
        else{
            root=i-1;
        }
    }
    cal(root);
    dfs(root);
    for(int i=0;i<n;i++){
        for(int j=0;j<log_n;j++){
            up[i][j]=-1;
        }
    }
    for(int i=0;i<n;i++){
        for(auto x:adj[i]){
            up[x][0]=i;
        }
    }
    for(int j=1;j<log_n;j++){
        for(int i=0;i<n;i++){
            if(up[i][j-1]>-1&&up[up[i][j-1]][j-1]>-1){
                up[i][j]=up[up[i][j-1]][j-1];
            }
        }
    }
    while(q--){
        int t;
        cin>>t;
        if(t==1){
            int k;
            cin>>k;
            for(int i=1;i<k;i++){
                op1();
            }
            cout<<op1()+1<<"\n";
        }
        else{
            int x;
            cin>>x;
            x--;
            cout<<op2(x)<<"\n";
        }
    }
}

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