oj.uz

Submission #31562

# Submission time Handle Problem Language Result Execution time Memory
31562 2017-08-29T11:54:55 Z chonka Ball Machine (BOI13_ballmachine) C++
20.9524 / 100
 349 ms 24088 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 15808 KB Output isn't correct
2 Incorrect 186 ms 17296 KB Output isn't correct
3 Incorrect 93 ms 17296 KB Output isn't correct
4 Incorrect 0 ms 15808 KB Output isn't correct
5 Incorrect 0 ms 15808 KB Output isn't correct
6 Incorrect 0 ms 15808 KB Output isn't correct
7 Incorrect 3 ms 15808 KB Output isn't correct
8 Incorrect 3 ms 15808 KB Output isn't correct
9 Incorrect 9 ms 15940 KB Output isn't correct
10 Incorrect 33 ms 16204 KB Output isn't correct
11 Incorrect 186 ms 17296 KB Output isn't correct
12 Incorrect 83 ms 17296 KB Output isn't correct
13 Incorrect 139 ms 17296 KB Output isn't correct

Subtask #2
10.7142857143 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 17316 KB Output is correct
2 Incorrect 253 ms 20568 KB Output isn't correct
3 Correct 116 ms 18216 KB Output is correct
4 Incorrect 129 ms 17308 KB Output isn't correct
5 Incorrect 113 ms 17172 KB Output isn't correct
6 Incorrect 99 ms 17176 KB Output isn't correct
7 Incorrect 93 ms 16816 KB Output isn't correct
8 Correct 46 ms 17320 KB Output is correct
9 Incorrect 213 ms 21256 KB Output isn't correct
10 Incorrect 256 ms 20568 KB Output isn't correct
11 Incorrect 206 ms 20572 KB Output isn't correct
12 Incorrect 236 ms 19588 KB Output isn't correct
13 Correct 133 ms 23168 KB Output is correct
14 Correct 96 ms 18216 KB Output is correct

Subtask #3
8.57142857143 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 126 ms 18388 KB Output isn't correct
2 Incorrect 349 ms 19656 KB Output isn't correct
3 Correct 186 ms 22520 KB Output is correct
4 Incorrect 163 ms 20276 KB Output isn't correct
5 Incorrect 216 ms 19972 KB Output isn't correct
6 Incorrect 199 ms 19980 KB Output isn't correct
7 Incorrect 179 ms 19040 KB Output isn't correct
8 Correct 146 ms 22524 KB Output is correct
9 Incorrect 263 ms 20988 KB Output isn't correct
10 Incorrect 263 ms 20572 KB Output isn't correct
11 Incorrect 289 ms 20584 KB Output isn't correct
12 Incorrect 289 ms 19660 KB Output isn't correct
13 Correct 289 ms 24088 KB Output is correct
14 Incorrect 233 ms 18220 KB Output isn't correct

Subtask #4
1.66666666667 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 259 ms 20988 KB Output isn't correct
2 Incorrect 229 ms 19660 KB Output isn't correct
3 Correct 136 ms 24084 KB Output is correct
4 Incorrect 223 ms 20988 KB Output isn't correct
5 Incorrect 239 ms 20576 KB Output isn't correct
6 Incorrect 209 ms 20576 KB Output isn't correct
7 Incorrect 266 ms 19660 KB Output isn't correct
8 Correct 129 ms 24088 KB Output is correct
9 Correct 119 ms 18220 KB Output is correct