Submission #153586

#	Time	Username	Problem	Language	Result	Execution time	Memory
153586		brcode	Ball Machine (BOI13_ballmachine)	C++14	100 / 100	696 ms	28092 KiB

ballmachine

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
int n,q;
int root;
const int MAXN = 1e5+5;
const int MAXK = 25;
vector<int> v1[MAXN];
int par[MAXN][MAXK];
int subtreemin[MAXN];

int currtime = 1;
bool occupied[MAXN];
int timer[MAXN];
int depth[MAXN];
bool cmp(int x,int y){
    return subtreemin[x]<subtreemin[y];
}
bool cmp2(int x,int y){
    return timer[x]<timer[y];
}
set<int,decltype(&cmp2)> s1(&cmp2);
void dfs(int curr){
    subtreemin[curr] = curr;
    for(int x:v1[curr]){
        depth[x] = depth[curr]+1;
        dfs(x);
        subtreemin[curr] = min(subtreemin[curr],subtreemin[x]);
    }
}
void dfs2(int curr){

    for(int x:v1[curr]){
        dfs2(x);
    }
    timer[curr] = currtime++;
    //cout<<curr<<" "<<timer[curr]<<endl;
    s1.insert(curr);
}
int addball(){
    int ans = *s1.begin();
    s1.erase(s1.begin());
    occupied[ans] = true;
    return ans;
}
int removeball(int x){
    int original = x;
    for(int i=19;i>=0;i--){
        if(par[x][i]!=-1 && occupied[par[x][i]]){
            x=par[x][i];
        }

    }
    occupied[x] = false;
    s1.insert(x);
    return depth[original]-depth[x];
}
int main(){
   cin>>n>>q;
   for(int i=1;i<=n;i++){
        int p;
        cin>>p;
        if(p==0){
            root = i;
            par[i][0] = -1;
            continue;
        }
        par[i][0] = p;
        v1[p].push_back(i);
   }
   depth[root] = 0;
   for(int i=1;i<=n;i++){
        subtreemin[i] = MAXN;

   }

   dfs(root);
   for(int i=1;i<=n;i++){
        sort(v1[i].begin(),v1[i].end(),cmp);
   }
   dfs2(root);
   for(int i=1;i<MAXK;i++){
        for(int j=1;j<=n;j++){
            if(par[j][i-1] == -1){
                par[j][i] = -1;
            }else{
                par[j][i] = par[par[j][i-1]][i-1];
            }
        }
   }
   for(int i=1;i<=q;i++){
        int t;
        cin>>t;
        if(t==1){
            int val;
            cin>>val;
            int x;
            for(int j=1;j<=val;j++){
                x = addball();
             //   cout<<123<<" "<<x<<endl;
            }
            cout<<x<<endl;
        }else{
            int val;
            cin>>val;
            cout<<removeball(val)<<endl;
        }
   }
}

Compilation message (stderr)

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

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