Submission #31892

#	Time	Username	Problem	Language	Result	Execution time	Memory
31892		chonka	Ball Machine (BOI13_ballmachine)	C++98	100 / 100	349 ms	25508 KiB

ballmachine

#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 (stderr)

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 / 25
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40
• Subtask 4: 5 / 5