Submission #40603

#	Time	Username	Problem	Language	Result	Execution time	Memory
40603		chonka	Birthday gift (IZhO18_treearray)	C++98	100 / 100	1419 ms	82516 KiB

treearray

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

#define MAXN 200007
#define LOG 20
int n , m , q ;
vector < int > v[ MAXN ] ;

int a[ MAXN ] ;

int lvl[ MAXN ] ;
int LCA[ MAXN ][ LOG + 2 ] ;
int f[ MAXN ] ;
set < int > s[ MAXN ] ;
set < int > aux[ MAXN ] ;


void dfs_init ( int vertex , int prv ) {
    int i ;
    int sz = v[ vertex ].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_init ( v[ vertex ][ i ] , vertex ) ;
    }
}

int get_LCA ( int x , int y ) {
    int i ;
    for ( i = LOG ; i >= 0 ; i -- ) {
        if ( ( lvl[ x ] - (1<<i) ) >= lvl[ y ] ) {
            x = LCA[ x ][ i ] ;
        }
        if ( ( lvl[ y ] - (1<<i) ) >= lvl[ x ] ) {
            y = LCA[ y ][ i ] ;
        }
    }
    for ( i = LOG ; i >= 0 ; i -- ) {
        if ( LCA[ x ][ i ] != LCA[ y ][ i ] ) {
            x = LCA[ x ][ i ] ;
            y = LCA[ y ][ i ] ;
        }
    }
    if ( x != y ) { x = LCA[ x ][ 0 ] ; }
    return x ;
}

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

void solve ( ) {
    dfs_init ( 1 , -1 ) ;
    int i ;
    for ( i = 1 ; i <= m - 1 ; i ++ ) {
        f[ i ] = get_LCA ( a[ i ] , a[ i + 1 ] ) ;
        s[ f[ i ] ].insert ( i ) ;
    }
    for ( i = 1 ; i <= m ; i ++ ) {
        aux[ a[ i ] ].insert ( i ) ;
    }
    int type , x , y , z ;
    while ( q != 0 ) {
        q -- ;
        scanf ( "%d" , &type ) ;
        if ( type == 1 ) {
            scanf ( "%d%d" , &x , &y ) ;
            aux[ a[ x ] ].erase ( x ) ;
            a[ x ] = y ;
            aux[ a[ x ] ].insert ( x ) ;
            if ( x != 1 ) {
                s[ f[ x - 1 ] ].erase ( x - 1 ) ;
                f[ x - 1 ] = get_LCA ( a[ x - 1 ] , a[ x ] ) ;
                s[ f[ x - 1 ] ].insert ( x - 1 ) ;
            }
            if ( x != m ) {
                s[ f[ x ] ].erase ( x ) ;
                f[ x ] = get_LCA ( a[ x ] , a[ x + 1 ] ) ;
                s[ f[ x ] ].insert ( x ) ;
            }
        }
        else {
            scanf ( "%d%d%d" , &x , &y , &z ) ;
            set < int > :: iterator it = s[ z ].lower_bound ( x ) ;
            set < int > :: iterator h = aux[ z ].lower_bound ( x ) ;
            if ( it != s[ z ].end ( ) && (*it) < y ) {
                printf ( "%d %d\n" , (*it) , (*it) + 1 ) ;
            }
            else if ( h != aux[ z ].end ( ) && (*h) <= y ) {
                printf ( "%d %d\n" , (*h) , (*h) ) ;
            }
            else { printf ( "-1 -1\n" ) ; }
        }
    }
}

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

Compilation message (stderr)

treearray.cpp: In function 'void input()':
treearray.cpp:58:39: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ( "%d%d%d" , &n , &m , &q ) ;
                                       ^
treearray.cpp:62:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf ( "%d%d" , &x , &y ) ;
                                    ^
treearray.cpp:67:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf ( "%d" , &a[ i ] ) ;
                                  ^
treearray.cpp: In function 'void solve()':
treearray.cpp:84:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf ( "%d" , &type ) ;
                                ^
treearray.cpp:86:40: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf ( "%d%d" , &x , &y ) ;
                                        ^
treearray.cpp:102:47: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf ( "%d%d%d" , &x , &y , &z ) ;
                                               ^

• Subtask 1: 12 / 12
• Subtask 2: 18 / 18
• Subtask 3: 26 / 26
• Subtask 4: 44 / 44