oj.uz

Submission #440720

# Submission time Handle Problem Language Result Execution time Memory
440720 2021-07-02T18:52:01 Z fadi57 Ball Machine (BOI13_ballmachine) C++14
100 / 100
 578 ms 35064 KB 
#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

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

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 395 ms 14756 KB Output is correct
3 Correct 323 ms 14468 KB Output is correct
4 Correct 3 ms 2664 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 4 ms 2784 KB Output is correct
7 Correct 7 ms 2764 KB Output is correct
8 Correct 5 ms 2800 KB Output is correct
9 Correct 25 ms 3424 KB Output is correct
10 Correct 73 ms 5616 KB Output is correct
11 Correct 451 ms 14636 KB Output is correct
12 Correct 316 ms 14512 KB Output is correct
13 Correct 391 ms 14836 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 8936 KB Output is correct
2 Correct 462 ms 27340 KB Output is correct
3 Correct 374 ms 19504 KB Output is correct
4 Correct 267 ms 10752 KB Output is correct
5 Correct 265 ms 10436 KB Output is correct
6 Correct 270 ms 10472 KB Output is correct
7 Correct 257 ms 9100 KB Output is correct
8 Correct 201 ms 9032 KB Output is correct
9 Correct 467 ms 27800 KB Output is correct
10 Correct 475 ms 27372 KB Output is correct
11 Correct 478 ms 27392 KB Output is correct
12 Correct 446 ms 23780 KB Output is correct
13 Correct 416 ms 30720 KB Output is correct
14 Correct 325 ms 19532 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 239 ms 15244 KB Output is correct
2 Correct 527 ms 24476 KB Output is correct
3 Correct 344 ms 28264 KB Output is correct
4 Correct 329 ms 22612 KB Output is correct
5 Correct 344 ms 22368 KB Output is correct
6 Correct 327 ms 22340 KB Output is correct
7 Correct 337 ms 19776 KB Output is correct
8 Correct 349 ms 28252 KB Output is correct
9 Correct 543 ms 27816 KB Output is correct
10 Correct 545 ms 27472 KB Output is correct
11 Correct 530 ms 27456 KB Output is correct
12 Correct 578 ms 24400 KB Output is correct
13 Correct 530 ms 35064 KB Output is correct
14 Correct 429 ms 20388 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 526 ms 27916 KB Output is correct
2 Correct 541 ms 24512 KB Output is correct
3 Correct 459 ms 34264 KB Output is correct
4 Correct 520 ms 27920 KB Output is correct
5 Correct 537 ms 27456 KB Output is correct
6 Correct 473 ms 27492 KB Output is correct
7 Correct 513 ms 24348 KB Output is correct
8 Correct 448 ms 34344 KB Output is correct
9 Correct 338 ms 19592 KB Output is correct