oj.uz

Submission #666834

# Submission time Handle Problem Language Result Execution time Memory
666834 2022-11-29T19:08:21 Z hyakup Ball Machine (BOI13_ballmachine) C++17
100 / 100
 202 ms 23380 KB 
#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 );
            
            int cont = 0, last;
            
            for( int i = 0; i < ordem.size(); i++ ){
                
                if( !tem_bola[ordem[i]] ){
                    
                    tem_bola[ ordem[i] ] = true;
                    cont++;
                    
                    last = ordem[i];
                    
                    if( cont == k ) break;
                }
                
            } 
            
            printf("%d\n", last );
            
        }
        else{
            
            int x; scanf("%d", &x );
            
            int qtd = quedas( x );
            
            printf("%d\n", qtd );
        }
    }
}

Compilation message

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:119:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |             for( int i = 0; i < ordem.size(); i++ ){
      |                             ~~^~~~~~~~~~~~~~
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:138:25: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  138 |             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
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 111 ms 11000 KB Output is correct
3 Correct 91 ms 11100 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2772 KB Output is correct
7 Correct 3 ms 2772 KB Output is correct
8 Correct 4 ms 2772 KB Output is correct
9 Correct 9 ms 3156 KB Output is correct
10 Correct 26 ms 4744 KB Output is correct
11 Correct 101 ms 10996 KB Output is correct
12 Correct 102 ms 11088 KB Output is correct
13 Correct 103 ms 10980 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 6644 KB Output is correct
2 Correct 195 ms 19040 KB Output is correct
3 Correct 117 ms 15320 KB Output is correct
4 Correct 64 ms 7756 KB Output is correct
5 Correct 64 ms 7764 KB Output is correct
6 Correct 59 ms 7712 KB Output is correct
7 Correct 69 ms 6848 KB Output is correct
8 Correct 39 ms 6620 KB Output is correct
9 Correct 165 ms 19048 KB Output is correct
10 Correct 173 ms 19012 KB Output is correct
11 Correct 180 ms 19064 KB Output is correct
12 Correct 185 ms 16800 KB Output is correct
13 Correct 114 ms 20724 KB Output is correct
14 Correct 88 ms 15384 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 11012 KB Output is correct
2 Correct 154 ms 17292 KB Output is correct
3 Correct 117 ms 19060 KB Output is correct
4 Correct 98 ms 16088 KB Output is correct
5 Correct 105 ms 15920 KB Output is correct
6 Correct 131 ms 15840 KB Output is correct
7 Correct 142 ms 14348 KB Output is correct
8 Correct 109 ms 19112 KB Output is correct
9 Correct 148 ms 19320 KB Output is correct
10 Correct 199 ms 19204 KB Output is correct
11 Correct 180 ms 19256 KB Output is correct
12 Correct 165 ms 17296 KB Output is correct
13 Correct 202 ms 23380 KB Output is correct
14 Correct 105 ms 15420 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 19308 KB Output is correct
2 Correct 164 ms 17268 KB Output is correct
3 Correct 156 ms 23008 KB Output is correct
4 Correct 163 ms 19344 KB Output is correct
5 Correct 158 ms 19204 KB Output is correct
6 Correct 165 ms 19204 KB Output is correct
7 Correct 165 ms 17232 KB Output is correct
8 Correct 135 ms 23104 KB Output is correct
9 Correct 106 ms 15476 KB Output is correct