Submission #440720

#	Time	Username	Problem	Language	Result	Execution time	Memory
440720		fadi57	Ball Machine (BOI13_ballmachine)	C++14	100 / 100	578 ms	35064 KiB

ballmachine

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
const int mx=1e5+5;
typedef long long ll;
const int mod=1e9+7;
int inf=1e9+10;
int n,l,r,q;
set<pair<int,int>>nxt;

int t=1;
int timm[mx];
int m[mx];
int mn[mx];
const int mxx=22;
vector<int>adj[mx];
int dp[mx][22];
void calcmin(int node){
 mn[node]=node;

    for(auto it:adj[node]){

        calcmin(it);
        mn[node]=min(mn[node],mn[it]);
    }
}

void dfs(int node){


     vector<pair<int,int>>ord;
     for(auto it:adj[node]){


        ord.push_back({mn[it],it});

     }
   sort(ord.begin(),ord.end());

   for(auto it:ord){

    dfs(it.second);
   }
  timm[node]=t;
  m[t]=node;
  nxt.insert({t,node});
  t++;
 }



 void dfs2(int node,int par){

 dp[node][0]=par;

 for(int i=1;i<mxx;i++){

    dp[node][i]=dp[dp[node][i-1]][i-1];
 }



 for(auto it:adj[node]){
    dfs2(it,node);
 }
 return;
 }
 int ball[mx];
 int main(){
     cin>>n>>q;
     for(int i=1;i<=n;i++){

        int x;
        cin>>x;
        if(x==0){r=i;}else{

            adj[x].push_back(i);


        }
     }
     calcmin(r);
     dfs(r);
     dfs2(r,0);

      for(int i=0;i<q;i++){
        int t;cin>>t;

        if(t==1){

            int k;
            cin>>k;
            int me;
            while(k--){
               auto me=*nxt.begin();
               nxt.erase(me);
               ball[me.second]=1;

               if(k==0){
                cout<<me.second;
               }
               // cout<<k<<" ";
            }
        }else{

        int v;cin>>v;
        int d=0;
        for(int i=mxx-1;i>=0;i--){
            if(!ball[dp[v][i]]){continue;
            }else{
                v=dp[v][i];
                d+=(1<<i);


            }


        }
        ball[v]=0;
        nxt.insert({timm[v],v});
        cout<<d;


           }


        cout<<"\n";

      }

 }

Compilation message (stderr)

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:94:17: warning: unused variable 'me' [-Wunused-variable]
   94 |             int me;
      |                 ^~

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