Submission #30859

#	Time	Username	Problem	Language	Result	Execution time	Memory
30859		Navick	Ball Machine (BOI13_ballmachine)	C++14	11.54 / 100	253 ms	28308 KiB

ballmachine

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10 , LG = 20;
int par[LG][N] , h[N] , st[N] , tim = 0 , root = -1 , f[N] , en[N] , mini[N];
bool used[N];
vector<int > child[N];
set<pair<int,int> > s;

bool cmp(int a,int b){
    return mini[a] < mini[b];
}

void p_dfs(int v,int p=0){
    mini[v] = v;
    for(auto u:child[v]){
        if(u == p)continue;
        p_dfs(u , v);
        mini[v] = min(mini[v] , mini[u]);
    }
}


void dfs(int v , int p = 0){

    par[0][v] = p;
    for(int i=1;i<LG;i++)par[i][v] = par[i-1][par[i-1][v]];

    st[v] = tim++;
    for(auto u:child[v]){
        h[u] = h[v] + 1;
        dfs(u , v);
    }
    en[v] = tim;
}


int i_par(int v,int x){
    for(int i = LG - 1; i>=0 ; i--){
        if(x & (1<<i))v = par[i][v];
    }
    return v;
}
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

    int n , q; cin>>n>>q;
    for(int i=1;i<=n;i++){
        int p; cin>>p;
        if(p == 0)root = i;
        else child[p].push_back(i);
    }

    p_dfs(root);

    for(int i=1;i<=n;i++)sort(child[i].begin() , child[i].end() , cmp);

    dfs(root);

    for(int i=1;i<=n;i++)s.insert({en[i] , -st[i]});

    for(int i=1;i<=n;i++)f[st[i]] = i;

    while(q--){
        int type; cin>>type;
        if(type == 1){
            int k , ind ; cin>>k;
            while(k--){
                ind = (*s.begin()).second; ind = -ind;
                s.erase(s.begin());
                used[ind] = true;
            }
            cout<<f[ind]<<'\n';
        }else{
            int v; cin>>v;
            int lo = 0 , hi = h[v] + 1;
            while(hi - lo > 1){
                int mid = (lo + hi)/2;
                int p = i_par(v , mid);
                if(used[st[p]] == true)lo = mid; else hi = mid;
            }
            int x = i_par(v , lo);
            used[st[x]] = false;
            cout<<h[v] - h[x]<<'\n';
            s.insert({en[x] , -st[x]});
        }
    }
}

Compilation message (stderr)

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:72:24: warning: 'ind' may be used uninitialized in this function [-Wmaybe-uninitialized]
             cout<<f[ind]<<'\n';
                        ^

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