Submission #58559

#	Time	Username	Problem	Language	Result	Execution time	Memory
58559		Batrr	Ball Machine (BOI13_ballmachine)	C++14	100 / 100	647 ms	35444 KiB

ballmachine

#include <bits/stdc++.h>
/*
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4")
*/
#define ll long long                   
#define f first 
#define s second 
#define pb push_back               
#define mp make_pair 
#define IOS ios_base::sync_with_stdio(0);

using namespace std;                    

const ll maxn=2e5+123,inf=1e18,mod=1e9+7,N=360360,LOG=20;
vector<int>g[maxn];
int n,q,root,was[maxn],depth[maxn],mn[maxn],ord[maxn],cur,up[maxn][LOG];
set< pair<int,int> > st;
void dfs1(int v){
    for(int i=1;i<LOG;i++)
        up[v][i]=up[up[v][i-1]][i-1];
    mn[v]=v;
    for(auto to:g[v]){
        up[to][0]=v;
        depth[to]=depth[v]+1;
        dfs1(to);
        mn[v]=min(mn[v],mn[to]);
    }   
}
void dfs2(int v){
    ord[v]=--cur;
    st.insert({ord[v],v});
    vector< pair<int,int> >vec;
    for( auto to:g[v] )
        vec.pb({-mn[to],to});
    sort(vec.begin(),vec.end());
    for( auto to:vec )
        dfs2(to.s);
}
int main(){
    #ifdef LOCAL
        freopen ("test.in", "r", stdin);
    #endif                                     
    IOS
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        int p;
        cin>>p;
        g[p].pb(i);
        if(p==0)
            root=i;
    }
    dfs1(root);
    dfs2(root);
    while(q--){
        int type,x,y;
        cin>>type>>x;
        if(type==1){
            while(x--){
                int v=(*st.begin()).s;
                st.erase(st.begin());
                was[v]=1;
                y=v;
            }
            cout<<y<<endl;
        }else{
            y=x;
            for(int i=LOG-1;i>=0;i--)
                if( was[up[x][i]] )
                    x=up[x][i];
            was[x]=0;
            st.insert({ord[x],x});              
            cout<<depth[y]-depth[x]<<endl;
        }
    }
}

Compilation message (stderr)

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:66:19: warning: 'y' may be used uninitialized in this function [-Wmaybe-uninitialized]
             cout<<y<<endl;
                   ^

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