Submission #666825

#	Time	Username	Problem	Language	Result	Execution time	Memory
666825		hyakup	Ball Machine (BOI13_ballmachine)	C++17	62.00 / 100	199 ms	23848 KiB

ballmachine

#include <bits/stdc++.h>
using namespace std;

#define pb push_back

const int maxn = 100010;
const int maxk = 20;
int n, q; 

vector<int> adj[maxn], ordem;
int minimo_da_sub[maxn];

bool tem_bola[maxn];

int dp[maxn][maxk], nivel[maxn];

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

void dfsInit( int cur, int pai ){
    
    minimo_da_sub[cur] = cur;
    
    dp[cur][0] = pai;
    
    for( int k = 1; k < maxk; k++ ) dp[cur][k] = dp[ dp[cur][ k - 1] ][k - 1]; 
    
    for( int i = 0; i < adj[cur].size(); i++ ){
        
        int viz = adj[cur][i];
        
        if( viz == pai ) continue;
        
        nivel[viz] = nivel[cur] + 1;
        
        dfsInit(viz, cur);
        
        minimo_da_sub[cur] = min( minimo_da_sub[viz], minimo_da_sub[cur] );
    
    }
    
    sort( adj[cur].begin(), adj[cur].end(), cmp );
    
}

void criaOrdem( int cur, int pai ){
    
    for( int i = 0; i < adj[cur].size(); i++ ){
        
        int viz = adj[cur][i];
        
        if( viz == pai ) continue;
        
        criaOrdem(viz, cur);
    
    }
    
    ordem.pb(cur);
}

int quedas( int x ){
    
    int x_ = x;
    
    for( int i = maxk - 1; i >= 0; i-- ){
        if( tem_bola[ dp[x_][i] ] ){
            
            x_ = dp[x_][i];
            
        }
    }
    
    tem_bola[x_] = false;
    
    return nivel[x] - nivel[x_];
}

int main(){
    
    scanf("%d %d", &n, &q );
    
    int root;
    
    for( int i = 1; i <= n; i++ ){
        
        int x; scanf("%d", &x );
        
        if( x == 0 ){
            
            root = i;
            
            continue;
        }
        
        adj[i].pb(x);
        adj[x].pb(i);
    }
    
    dfsInit( root, root );
    
    criaOrdem( root, root );
    
    //for( int i = 0; i < n; i++ ) printf("%d ", ordem[i] );
    
    //printf("\n");
    
    for( int i = 0; i < q; i++ ){
        
        int t; scanf("%d", &t );
        
        if( t == 1 ){
            
            int k; scanf("%d", &k );
            
            for( int i = 0; i < k; i++ ) tem_bola[ ordem[i] ] = true;
            
            printf("%d\n", ordem[k - 1] );
            
        }
        else{
            
            int x; scanf("%d", &x );
            
            int qtd = quedas( x );
            
            printf("%d\n", qtd );
        }
    }
}

Compilation message (stderr)

ballmachine.cpp: In function 'void dfsInit(int, int)':
ballmachine.cpp:30:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |     for( int i = 0; i < adj[cur].size(); i++ ){
      |                     ~~^~~~~~~~~~~~~~~~~
ballmachine.cpp: In function 'void criaOrdem(int, int)':
ballmachine.cpp:50:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |     for( int i = 0; i < adj[cur].size(); i++ ){
      |                     ~~^~~~~~~~~~~~~~~~~
ballmachine.cpp: In function 'int main()':
ballmachine.cpp:82:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |     scanf("%d %d", &n, &q );
      |     ~~~~~^~~~~~~~~~~~~~~~~~
ballmachine.cpp:88:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |         int x; scanf("%d", &x );
      |                ~~~~~^~~~~~~~~~~
ballmachine.cpp:111:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  111 |         int t; scanf("%d", &t );
      |                ~~~~~^~~~~~~~~~~
ballmachine.cpp:115:25: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  115 |             int k; scanf("%d", &k );
      |                    ~~~~~^~~~~~~~~~~
ballmachine.cpp:124:25: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  124 |             int x; scanf("%d", &x );
      |                    ~~~~~^~~~~~~~~~~
ballmachine.cpp:103:14: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
  103 |     criaOrdem( root, root );
      |     ~~~~~~~~~^~~~~~~~~~~~~~

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