oj.uz

Submission #31892

# Submission time Handle Problem Language Result Execution time Memory
31892 2017-09-12T13:27:05 Z chonka Ball Machine (BOI13_ballmachine) C++
100 / 100
 349 ms 25508 KB 
#include<iostream>
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std ;


#define MAXN 100007
#define LOG 22


int n , q ;
vector < int > v[ MAXN ] ;

int root ;
int subtree[ MAXN ] ;
int lvl[ MAXN ] ;
int prv[ MAXN ][ LOG ] ;
int rev[ MAXN ] ;

vector < int > ord ;
bool used[ MAXN ] ;

bool cmp ( int x , int y ) {
    return ( subtree[ x ] < subtree[ y ] ) ;
}

void init ( int vertex , int lst ) {
    subtree[ vertex ] = vertex ;
    int i ;
    int sz = v[ vertex ].size ( ) ;
    if ( lst != -1 ) {
        for ( i = 1 ; i < LOG ; i ++ ) {
            prv[ vertex ][ i ] = prv[ prv[ vertex ][ i - 1 ] ][ i - 1 ] ;
        }
    }
    for ( i = 0 ; i < sz ; i ++ ) {
        if ( v[ vertex ][ i ] == lst ) { continue ; }
        prv[ v[ vertex ][ i ] ][ 0 ] = vertex ;
        lvl[ v[ vertex ][ i ] ] = lvl[ vertex ] + 1 ;
        init ( v[ vertex ][ i ] , vertex ) ;
        subtree[ vertex ] = min ( subtree[ vertex ] , subtree[ v[ vertex ][ i ] ] ) ;
    }
}


void dfs ( int vertex , int lst ) {
    int i ;
    int sz = v[ vertex ].size ( ) ;
    for ( i = 0 ; i < sz ; i ++ ) {
        if ( v[ vertex ][ i ] == lst ) { continue ; }
        dfs ( v[ vertex ][ i ] , vertex ) ;
    }
    ord.push_back ( vertex ) ;
    rev[ vertex ] = ord.size ( ) ;
}

class Tree {
    public :
    int tr[ 3 * MAXN ] ;
    void init ( int where , int IL , int IR ) {
        tr[ where ] = 0 ;
        if ( IL == IR ) { return ; }
        int mid = ( IL + IR ) / 2 ;
        init ( 2 * where , IL , mid ) ;
        init ( 2 * where + 1 , mid + 1 , IR ) ;
    }
    void update ( int where , int IL , int IR , int pos , int val ) {
        if ( IR < pos || pos < IL ) { return ; }
        if ( IL == IR ) { tr[ where ] += val ; return ; }
        int mid = ( IL + IR ) / 2 ;
        if ( pos <= mid ) { update ( 2 * where , IL , mid , pos , val ) ; }
        else { update ( 2 * where + 1 , mid + 1 , IR , pos , val ) ; }
        tr[ where ] += val ;
    }
    int query ( int where , int IL , int IR ) {
        if ( tr[ where ] == ( IR - IL + 1 ) ) { return -1 ; }
        if ( IL == IR ) { return IL ; }
        int mid = ( IL + IR ) / 2 ;
        int ret = query ( 2 * where , IL , mid ) ;
        if ( ret != -1 ) { return ret ; }
        return query ( 2 * where + 1 , mid + 1 , IR ) ;
    }
};
Tree w ;

int get ( int x ) {
    int i ;
    for ( i = LOG - 1 ; i >= 0 ; i -- ) {
        int u = prv[ x ][ i ] ;
        if ( u == 0 ) { continue ; }
        if ( used[ u ] == true ) { x = u ; }
    }
    return x ;
}

void input ( ) {
    scanf ( "%d%d" , &n , &q ) ;
    int i ;
    for ( i = 1 ; i <= n ; i ++ ) {
        int x ;
        scanf ( "%d" , &x ) ;
        if ( x == 0 ) { root = i ; }
        else {
            v[ x ].push_back ( i ) ;
            v[ i ].push_back ( x ) ;
        }
    }
}

void solve ( ) {
    init ( root , -1 ) ;
    int i ;
    for ( i = 1 ; i <= n ; i ++ ) {
        sort ( v[ i ].begin ( ) , v[ i ].end ( ) , cmp ) ;
    }
    dfs ( root , -1 ) ;
    w.init ( 1 , 1 , n ) ;
    while ( q != 0 ) {
        q -- ;
        int x , y ;
        scanf ( "%d%d" , &x , &y ) ;
        if ( x == 1 ) {
            while ( y != 0 ) {
                y -- ;
                int id = w.query ( 1 , 1 , n ) ;
                if ( y == 0 ) { printf ( "%d\n" , ord[ id - 1 ] ) ; }
                if ( id == -1 ) { break ; }
                used[ ord[ id - 1 ] ] = 1 ;
                w.update ( 1 , 1 , n , id , 1 ) ;
            }
        }
        else {
            int id = get ( y ) ;
            used[ id ] = 0 ;
            w.update ( 1 , 1 , n , rev[ id ] , -1 ) ;
            printf ( "%d\n" , lvl[ y ] - lvl[ id ] ) ;
        }
    }
}

int main ( ) {
    input ( ) ;
    solve ( ) ;
    return 0 ;
}

Compilation message

ballmachine.cpp: In function 'void input()':
ballmachine.cpp:98:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ( "%d%d" , &n , &q ) ;
                                ^
ballmachine.cpp:102:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf ( "%d" , &x ) ;
                             ^
ballmachine.cpp: In function 'void solve()':
ballmachine.cpp:122:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf ( "%d%d" , &x , &y ) ;
                                    ^

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 15408 KB Output is correct
2 Correct 256 ms 17920 KB Output is correct
3 Correct 123 ms 17920 KB Output is correct
4 Correct 0 ms 15408 KB Output is correct
5 Correct 0 ms 15408 KB Output is correct
6 Correct 3 ms 15408 KB Output is correct
7 Correct 0 ms 15408 KB Output is correct
8 Correct 3 ms 15408 KB Output is correct
9 Correct 6 ms 15540 KB Output is correct
10 Correct 26 ms 16124 KB Output is correct
11 Correct 196 ms 17920 KB Output is correct
12 Correct 123 ms 17920 KB Output is correct
13 Correct 149 ms 17920 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 17216 KB Output is correct
2 Correct 269 ms 22408 KB Output is correct
3 Correct 139 ms 19768 KB Output is correct
4 Correct 109 ms 17416 KB Output is correct
5 Correct 93 ms 17428 KB Output is correct
6 Correct 93 ms 17436 KB Output is correct
7 Correct 99 ms 16796 KB Output is correct
8 Correct 53 ms 17220 KB Output is correct
9 Correct 259 ms 22440 KB Output is correct
10 Correct 273 ms 22408 KB Output is correct
11 Correct 256 ms 22408 KB Output is correct
12 Correct 266 ms 20732 KB Output is correct
13 Correct 176 ms 24412 KB Output is correct
14 Correct 136 ms 19768 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 18908 KB Output is correct
2 Correct 349 ms 20852 KB Output is correct
3 Correct 236 ms 23632 KB Output is correct
4 Correct 169 ms 21176 KB Output is correct
5 Correct 193 ms 21152 KB Output is correct
6 Correct 189 ms 21160 KB Output is correct
7 Correct 166 ms 19908 KB Output is correct
8 Correct 159 ms 23632 KB Output is correct
9 Correct 239 ms 22440 KB Output is correct
10 Correct 246 ms 22412 KB Output is correct
11 Correct 309 ms 22416 KB Output is correct
12 Correct 243 ms 20844 KB Output is correct
13 Correct 279 ms 25508 KB Output is correct
14 Correct 213 ms 19780 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 239 ms 22440 KB Output is correct
2 Correct 269 ms 20848 KB Output is correct
3 Correct 199 ms 25508 KB Output is correct
4 Correct 296 ms 22444 KB Output is correct
5 Correct 266 ms 22416 KB Output is correct
6 Correct 259 ms 22408 KB Output is correct
7 Correct 299 ms 20852 KB Output is correct
8 Correct 189 ms 25508 KB Output is correct
9 Correct 136 ms 19780 KB Output is correct