Submission #713146

#	Time	Username	Problem	Language	Result	Execution time	Memory
713146		JJAnawat	Ball Machine (BOI13_ballmachine)	C++17	100 / 100	360 ms	25220 KiB

ballmachine

#include<bits/stdc++.h>

using namespace std;

int pa[100005][18];
vector<int> g[100005];
int mn[100005];
int tout[100005],ord[100005],counter=0;
set<int> s;

void dfs1(int u){
    mn[u]=u;
    for(auto v:g[u]){
        dfs1(v);
        mn[u]=min(mn[u],mn[v]);
    }
}

void dfs2(int u){
    for(auto v:g[u])
        dfs2(v);
    tout[u]=++counter;
    ord[counter]=u;
}

main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n,q;
    cin >> n >> q;
    int rt=0;
    for(int i=1,x;i<=n;i++){
        cin >> x;
        pa[i][0]=x;
        if(!x)
            rt=i;
        else
            g[x].push_back(i);
    }
    dfs1(rt);
    for(int i=1;i<=n;i++){
        sort(g[i].begin(),g[i].end(),[&](int x,int y){
            return mn[x]<mn[y];
        });
    }
    for(int j=1;j<18;j++)
        for(int i=1;i<=n;i++)
            pa[i][j]=pa[pa[i][j-1]][j-1];
    dfs2(rt);
    for(int i=1;i<=n;i++)
        s.insert(i);
    int t,x,ans;
    while(q--){
        cin >> t >> x;
        if(t==1){
            ans=0;
            while(x--){
                ans=*s.begin();
                s.erase(s.begin());
            }
            cout << ord[ans] << "\n";
        }
        else{
            ans=0;
            for(int i=17;i>=0;i--){
                int px=pa[x][i];
                if(px!=0&&s.find(tout[px])==s.end()){
                    ans+=(1<<i);
                    x=px;
                }
            }
            s.insert(tout[x]);
            cout << ans << "\n";
        }
    }
}

Compilation message (stderr)

ballmachine.cpp:26:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   26 | main(){
      | ^~~~

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