Submission #854872

#	Time	Username	Problem	Language	Result	Execution time	Memory
854872		Essa2006	Ball Machine (BOI13_ballmachine)	C++14	100 / 100	290 ms	32716 KiB

ballmachine

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define FF first
#define SS second
#define all(a) a.begin(), a.end()
#define mod (ll)(1000000007)
const int lg=20;
int n, q, cur;
vector<int>P, Has_ball, Mn;
vector<vector<int> >A, Up;
priority_queue<array<int, 2> >pq;
map<int, int>mp;

void pre(){
    P.clear(), Has_ball.clear(), Mn.clear(), A.clear(), Up.clear(), mp.clear();
    P.resize(n+1), Has_ball.resize(n+1), Mn.resize(n+1), A.resize(n+1), Up.resize(n+1, vector<int>(lg+1));
}

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

void dfs(int u){
    Mn[u]=u;
    Up[u][0]=P[u];
    for(int j=1;j<=lg;j++){
        Up[u][j]=Up[Up[u][j-1]][j-1];
    }
    for(auto v:A[u]){
        dfs(v);
        Mn[u]=min(Mn[u], Mn[v]);
    }
    sort(all(A[u]), cmp);
    
}


void ord(int u){
    for(auto v:A[u]){
        ord(v);
    }
    mp[u]=cur;
    array<int, 2>a={-cur, u};
    pq.push(a);
    cur++;
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>q;
    pre();
    int root;
    for(int i=1;i<=n;i++){
        int p, u=i;
        cin>>p;
        if(!p)
            root=u;
        else{
            A[p].push_back(u);
            P[u]=p;
        }
    }
    dfs(root), ord(root);
    while(q--){
        int type, k;
        cin>>type>>k;
        int ans=0;
        if(type==1){
            // add k balls and print the last postion
            while(k--){
                int u=pq.top()[1];
                pq.pop();
                Has_ball[u]=1;
                ans=u;
            }
        }
        else if(type==2){
            // remove ball in node k and print the number of balls in nodes above node k
            for(int j=lg;j>=0;j--){
                int v=Up[k][j];
                if(Has_ball[v])
                    ans+=(1<<j), k=v;
            }
            Has_ball[k]=0;
            array<int, 2>a={-mp[k], k};
            pq.push(a);
        }
        cout<<ans<<endl;
    }
}

Compilation message (stderr)

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:65:19: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
   65 |     dfs(root), ord(root);
      |                ~~~^~~~~~

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