Submission #55474

#	Time	Username	Problem	Language	Result	Execution time	Memory
55474		Diuven	Ball Machine (BOI13_ballmachine)	C++11	100 / 100	323 ms	26796 KiB

ballmachine

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MX=100010, inf=2e9;

int n, q, root;
vector<int> G[MX];
int nu[MX], re[MX], mn[MX];
int st[MX][20];

void dfs1(int v){
    mn[v]=v;
    for(int i=1; i<20; i++) st[v][i]=st[st[v][i-1]][i-1];
    for(int x:G[v]) dfs1(x), mn[v]=min(mn[v], mn[x]);
    sort(G[v].begin(), G[v].end(), [](int a, int b){ return mn[a]<mn[b]; });
}
void dfs2(int v){
    static int now=0;
    for(int x:G[v]) dfs2(x);
    nu[v]=++now; re[nu[v]]=v;
}

set<int> S;
bool B[MX];

int put(){
    int x=*S.begin();
    S.erase(x);
    int v=re[x];
    B[v]=true;
    // cout<<"PLACED: "<<v<<'\n';
    return v;
}

int pop(int v){
    int dist=0;
    for(int i=19; i>=0; i--) if(B[st[v][i]]) v=st[v][i], dist+=(1<<i);
    S.insert(nu[v]);
    B[v]=false;
    return dist;
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    cin>>n>>q;
    for(int i=1; i<=n; i++){
        int p; cin>>p;
        if(p==0) root=i;
        else G[p].push_back(i);
        st[i][0]=p;
    }
    dfs1(root); dfs2(root);
    for(int i=1; i<=n; i++) S.insert(i);

    // for(int i=1; i<=n; i++) cout<<nu[i]<<' ';
    // cout<<'\n';

    for(int i=1; i<=q; i++){
        int t, x; cin>>t>>x;
        if(t==1){
            int ans=0;
            for(; x--; ) ans=put();
            cout<<ans<<'\n';
        }
        else{
            cout<<pop(x)<<'\n';
        }
    }
    return 0;
}

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