Submission #31562

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

ballmachine

#include<iostream>
#include<stdio.h>
#include<vector>
using namespace std ;

#define MAXN 100007
#define LOG 22

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

int LCA[ MAXN ][ LOG ] ;
int lvl[ MAXN ] ;

int st[ MAXN ] ;
int en[ MAXN ] ;

int root ;

int sub[ MAXN ] ;

bool used[ MAXN ] ;

class Tree {
    public :
    int tr[ 3 * MAXN ] ;
    void merge ( int where ) {
        if ( tr[ 2 * where ] == MAXN ) { tr[ where ] = tr[ 2 * where + 1 ] ; }
        else if ( tr[ 2 * where + 1 ] == MAXN ) { tr[ where ] = tr[ 2 * where ] ; }
        else {
            tr[ where ] = min ( tr[ 2 * where ] , tr[ 2 * where + 1 ] ) ;
        }
    }
    void init ( int where , int IL , int IR ) {
        if ( IL == IR ) {
            int vertex = ord[ IL - 1 ] ;
            if ( sub[ vertex ] == 0 ) {
                tr[ where ] = vertex ;
            }
            else { tr[ where ] = MAXN ; }
            return ;
        }
        int mid = ( IL + IR ) / 2 ;
        init ( 2 * where , IL , mid ) ;
        init ( 2 * where + 1 , mid + 1 , IR ) ;
        merge ( where ) ;
    }
    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 ) ;
        }
        merge ( where ) ;
    }
    int query ( int where , int IL , int IR , int CURL , int CURR ) {
        if ( IR < CURL || CURR < IL ) {
            return MAXN ;
        }
        if ( CURL <= IL && IR <= CURR ) {
            return tr[ where ] ;
        }
        int mid = ( IL + IR ) / 2 ;
        return min ( query ( 2 * where , IL , mid , CURL , CURR ) , query ( 2 * where + 1 , mid + 1 , IR , CURL , CURR ) ) ;
    }
};
Tree w ;

int get_lst ( int vertex ) {
    int i ;
    for ( i = LOG - 1 ; i >= 0 ; i -- ) {
        int u = LCA[ vertex ][ i ] ;
        if ( used[ u ] == true ) { vertex = u ; }
    }
    return vertex ;
}

void dfs ( int vertex , int prv ) {
    int i ;
    int sz = v[ vertex ].size ( ) ;
    ord.push_back ( vertex ) ;
    st[ vertex ] = ord.size ( ) ;
    if ( prv != -1 ) {
        for ( i = 1 ; i < LOG ; i ++ ) {
            LCA[ vertex ][ i ] = LCA[ LCA[ vertex ][ i - 1 ] ][ i - 1 ] ;
        }
    }
    for ( i = 0 ; i < sz ; i ++ ) {
        if ( v[ vertex ][ i ] == prv ) { continue ; }
        lvl[ v[ vertex ][ i ] ] = lvl[ vertex ] + 1 ;
        LCA[ v[ vertex ][ i ] ][ 0 ] = vertex ;
        dfs ( v[ vertex ][ i ] , vertex ) ;
    }
    en[ vertex ] = ord.size ( ) ;
}

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 ; continue ; }
        sub[ x ] ++ ;
        v[ x ].push_back ( i ) ;
    }
}


void solve ( ) {
    dfs ( root , -1 ) ;
    w.init ( 1 , 1 , n ) ;
    int type , x ;
    while ( q != 0 ) {
        q -- ;
        scanf ( "%d%d" , &type , &x ) ;
        if ( type == 1 ) {
            while ( x != 0 ) {
                x -- ;
                int ret = w.query ( 1 , 1 , n , st[ root ] , en[ root ] ) ;
                if ( x == 0 ) {
                    printf ( "%d\n" , ret ) ;
                }
                used[ ret ] = true ;
                w.update ( 1 , 1 , n , st[ ret ] , MAXN ) ;
                if ( ret != root ) {
                    sub[ LCA[ ret ][ 0 ] ] -- ;
                    if ( sub[ LCA[ ret ][ 0 ] ] == 0 ) {
                        w.update ( 1 , 1 , n , st[ LCA[ ret ][ 0 ] ] , LCA[ ret ][ 0 ] ) ;
                    }
                }
            }
        }
        else {
            int ret = get_lst ( x ) ;
            printf ( "%d\n" , lvl[ x ] - lvl[ ret ] ) ;
            w.update ( 1 , 1 , n , st[ ret ] , ret ) ;
            used[ ret ] = false ;
            if ( ret != root ) {
                sub[ LCA[ ret ][ 0 ] ] ++ ;
                if ( sub[ LCA[ ret ][ 0 ] ] == 1 ) {
                    w.update ( 1 , 1 , n , st[ LCA[ ret ][ 0 ] ] , MAXN ) ;
                }
            }
        }
    }
}


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

Compilation message (stderr)

ballmachine.cpp: In function 'void input()':
ballmachine.cpp:106: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:110: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:124:39: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf ( "%d%d" , &type , &x ) ;
                                       ^

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