oj.uz

Submission #40603

# Submission time Handle Problem Language Result Execution time Memory
40603 2018-02-05T13:50:29 Z chonka Birthday gift (IZhO18_treearray) C++
100 / 100
 1419 ms 82516 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 21 ms 23784 KB n=5
2 Correct 20 ms 23904 KB n=100
3 Correct 20 ms 23976 KB n=100
4 Correct 20 ms 24048 KB n=100
5 Correct 21 ms 24084 KB n=100
6 Correct 21 ms 24084 KB n=100
7 Correct 21 ms 24092 KB n=100
8 Correct 21 ms 24092 KB n=100
9 Correct 28 ms 24092 KB n=100
10 Correct 20 ms 24092 KB n=100
11 Correct 23 ms 24092 KB n=100
12 Correct 21 ms 24092 KB n=100
13 Correct 20 ms 24092 KB n=100
14 Correct 21 ms 24092 KB n=100
15 Correct 22 ms 24092 KB n=100
16 Correct 21 ms 24092 KB n=100
17 Correct 20 ms 24092 KB n=100
18 Correct 21 ms 24092 KB n=100
19 Correct 22 ms 24092 KB n=100
20 Correct 21 ms 24092 KB n=100
21 Correct 20 ms 24092 KB n=100
22 Correct 22 ms 24092 KB n=100
23 Correct 22 ms 24092 KB n=100
24 Correct 21 ms 24092 KB n=100
25 Correct 23 ms 24092 KB n=100
26 Correct 21 ms 24092 KB n=12
27 Correct 21 ms 24092 KB n=100

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 23784 KB n=5
2 Correct 20 ms 23904 KB n=100
3 Correct 20 ms 23976 KB n=100
4 Correct 20 ms 24048 KB n=100
5 Correct 21 ms 24084 KB n=100
6 Correct 21 ms 24084 KB n=100
7 Correct 21 ms 24092 KB n=100
8 Correct 21 ms 24092 KB n=100
9 Correct 28 ms 24092 KB n=100
10 Correct 20 ms 24092 KB n=100
11 Correct 23 ms 24092 KB n=100
12 Correct 21 ms 24092 KB n=100
13 Correct 20 ms 24092 KB n=100
14 Correct 21 ms 24092 KB n=100
15 Correct 22 ms 24092 KB n=100
16 Correct 21 ms 24092 KB n=100
17 Correct 20 ms 24092 KB n=100
18 Correct 21 ms 24092 KB n=100
19 Correct 22 ms 24092 KB n=100
20 Correct 21 ms 24092 KB n=100
21 Correct 20 ms 24092 KB n=100
22 Correct 22 ms 24092 KB n=100
23 Correct 22 ms 24092 KB n=100
24 Correct 21 ms 24092 KB n=100
25 Correct 23 ms 24092 KB n=100
26 Correct 21 ms 24092 KB n=12
27 Correct 21 ms 24092 KB n=100
28 Correct 22 ms 24156 KB n=500
29 Correct 26 ms 24156 KB n=500
30 Correct 22 ms 24160 KB n=500
31 Correct 25 ms 24284 KB n=500
32 Correct 21 ms 24284 KB n=500
33 Correct 20 ms 24284 KB n=500
34 Correct 23 ms 24284 KB n=500
35 Correct 21 ms 24284 KB n=500
36 Correct 20 ms 24284 KB n=500
37 Correct 20 ms 24284 KB n=500
38 Correct 22 ms 24284 KB n=500
39 Correct 23 ms 24284 KB n=500
40 Correct 25 ms 24284 KB n=500
41 Correct 22 ms 24284 KB n=500
42 Correct 25 ms 24284 KB n=500
43 Correct 22 ms 24284 KB n=500
44 Correct 20 ms 24284 KB n=500
45 Correct 20 ms 24284 KB n=500
46 Correct 21 ms 24284 KB n=500
47 Correct 20 ms 24284 KB n=500
48 Correct 20 ms 24284 KB n=500
49 Correct 20 ms 24284 KB n=500
50 Correct 21 ms 24284 KB n=500
51 Correct 20 ms 24284 KB n=500
52 Correct 20 ms 24284 KB n=500
53 Correct 20 ms 24284 KB n=500
54 Correct 20 ms 24284 KB n=500
55 Correct 21 ms 24284 KB n=278
56 Correct 20 ms 24284 KB n=500
57 Correct 20 ms 24284 KB n=500
58 Correct 20 ms 24284 KB n=500

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 23784 KB n=5
2 Correct 20 ms 23904 KB n=100
3 Correct 20 ms 23976 KB n=100
4 Correct 20 ms 24048 KB n=100
5 Correct 21 ms 24084 KB n=100
6 Correct 21 ms 24084 KB n=100
7 Correct 21 ms 24092 KB n=100
8 Correct 21 ms 24092 KB n=100
9 Correct 28 ms 24092 KB n=100
10 Correct 20 ms 24092 KB n=100
11 Correct 23 ms 24092 KB n=100
12 Correct 21 ms 24092 KB n=100
13 Correct 20 ms 24092 KB n=100
14 Correct 21 ms 24092 KB n=100
15 Correct 22 ms 24092 KB n=100
16 Correct 21 ms 24092 KB n=100
17 Correct 20 ms 24092 KB n=100
18 Correct 21 ms 24092 KB n=100
19 Correct 22 ms 24092 KB n=100
20 Correct 21 ms 24092 KB n=100
21 Correct 20 ms 24092 KB n=100
22 Correct 22 ms 24092 KB n=100
23 Correct 22 ms 24092 KB n=100
24 Correct 21 ms 24092 KB n=100
25 Correct 23 ms 24092 KB n=100
26 Correct 21 ms 24092 KB n=12
27 Correct 21 ms 24092 KB n=100
28 Correct 22 ms 24156 KB n=500
29 Correct 26 ms 24156 KB n=500
30 Correct 22 ms 24160 KB n=500
31 Correct 25 ms 24284 KB n=500
32 Correct 21 ms 24284 KB n=500
33 Correct 20 ms 24284 KB n=500
34 Correct 23 ms 24284 KB n=500
35 Correct 21 ms 24284 KB n=500
36 Correct 20 ms 24284 KB n=500
37 Correct 20 ms 24284 KB n=500
38 Correct 22 ms 24284 KB n=500
39 Correct 23 ms 24284 KB n=500
40 Correct 25 ms 24284 KB n=500
41 Correct 22 ms 24284 KB n=500
42 Correct 25 ms 24284 KB n=500
43 Correct 22 ms 24284 KB n=500
44 Correct 20 ms 24284 KB n=500
45 Correct 20 ms 24284 KB n=500
46 Correct 21 ms 24284 KB n=500
47 Correct 20 ms 24284 KB n=500
48 Correct 20 ms 24284 KB n=500
49 Correct 20 ms 24284 KB n=500
50 Correct 21 ms 24284 KB n=500
51 Correct 20 ms 24284 KB n=500
52 Correct 20 ms 24284 KB n=500
53 Correct 20 ms 24284 KB n=500
54 Correct 20 ms 24284 KB n=500
55 Correct 21 ms 24284 KB n=278
56 Correct 20 ms 24284 KB n=500
57 Correct 20 ms 24284 KB n=500
58 Correct 20 ms 24284 KB n=500
59 Correct 26 ms 24540 KB n=2000
60 Correct 24 ms 24668 KB n=2000
61 Correct 24 ms 24668 KB n=2000
62 Correct 24 ms 24668 KB n=2000
63 Correct 25 ms 24668 KB n=2000
64 Correct 25 ms 24668 KB n=2000
65 Correct 24 ms 24668 KB n=2000
66 Correct 24 ms 24668 KB n=2000
67 Correct 25 ms 24668 KB n=2000
68 Correct 24 ms 24668 KB n=2000
69 Correct 23 ms 24668 KB n=2000
70 Correct 23 ms 24668 KB n=2000
71 Correct 23 ms 24668 KB n=2000
72 Correct 22 ms 24668 KB n=2000
73 Correct 24 ms 24668 KB n=2000
74 Correct 27 ms 24668 KB n=1844
75 Correct 22 ms 24668 KB n=2000
76 Correct 24 ms 24668 KB n=2000
77 Correct 23 ms 24668 KB n=2000
78 Correct 24 ms 24668 KB n=2000
79 Correct 27 ms 24668 KB n=2000
80 Correct 25 ms 24668 KB n=2000
81 Correct 26 ms 24668 KB n=2000
82 Correct 26 ms 24668 KB n=2000
83 Correct 24 ms 24736 KB n=2000
84 Correct 23 ms 24736 KB n=2000
85 Correct 25 ms 24736 KB n=2000
86 Correct 30 ms 24736 KB n=2000
87 Correct 30 ms 24736 KB n=2000
88 Correct 26 ms 24736 KB n=2000
89 Correct 28 ms 24736 KB n=2000
90 Correct 25 ms 24736 KB n=2000
91 Correct 24 ms 24736 KB n=2000

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 23784 KB n=5
2 Correct 20 ms 23904 KB n=100
3 Correct 20 ms 23976 KB n=100
4 Correct 20 ms 24048 KB n=100
5 Correct 21 ms 24084 KB n=100
6 Correct 21 ms 24084 KB n=100
7 Correct 21 ms 24092 KB n=100
8 Correct 21 ms 24092 KB n=100
9 Correct 28 ms 24092 KB n=100
10 Correct 20 ms 24092 KB n=100
11 Correct 23 ms 24092 KB n=100
12 Correct 21 ms 24092 KB n=100
13 Correct 20 ms 24092 KB n=100
14 Correct 21 ms 24092 KB n=100
15 Correct 22 ms 24092 KB n=100
16 Correct 21 ms 24092 KB n=100
17 Correct 20 ms 24092 KB n=100
18 Correct 21 ms 24092 KB n=100
19 Correct 22 ms 24092 KB n=100
20 Correct 21 ms 24092 KB n=100
21 Correct 20 ms 24092 KB n=100
22 Correct 22 ms 24092 KB n=100
23 Correct 22 ms 24092 KB n=100
24 Correct 21 ms 24092 KB n=100
25 Correct 23 ms 24092 KB n=100
26 Correct 21 ms 24092 KB n=12
27 Correct 21 ms 24092 KB n=100
28 Correct 22 ms 24156 KB n=500
29 Correct 26 ms 24156 KB n=500
30 Correct 22 ms 24160 KB n=500
31 Correct 25 ms 24284 KB n=500
32 Correct 21 ms 24284 KB n=500
33 Correct 20 ms 24284 KB n=500
34 Correct 23 ms 24284 KB n=500
35 Correct 21 ms 24284 KB n=500
36 Correct 20 ms 24284 KB n=500
37 Correct 20 ms 24284 KB n=500
38 Correct 22 ms 24284 KB n=500
39 Correct 23 ms 24284 KB n=500
40 Correct 25 ms 24284 KB n=500
41 Correct 22 ms 24284 KB n=500
42 Correct 25 ms 24284 KB n=500
43 Correct 22 ms 24284 KB n=500
44 Correct 20 ms 24284 KB n=500
45 Correct 20 ms 24284 KB n=500
46 Correct 21 ms 24284 KB n=500
47 Correct 20 ms 24284 KB n=500
48 Correct 20 ms 24284 KB n=500
49 Correct 20 ms 24284 KB n=500
50 Correct 21 ms 24284 KB n=500
51 Correct 20 ms 24284 KB n=500
52 Correct 20 ms 24284 KB n=500
53 Correct 20 ms 24284 KB n=500
54 Correct 20 ms 24284 KB n=500
55 Correct 21 ms 24284 KB n=278
56 Correct 20 ms 24284 KB n=500
57 Correct 20 ms 24284 KB n=500
58 Correct 20 ms 24284 KB n=500
59 Correct 26 ms 24540 KB n=2000
60 Correct 24 ms 24668 KB n=2000
61 Correct 24 ms 24668 KB n=2000
62 Correct 24 ms 24668 KB n=2000
63 Correct 25 ms 24668 KB n=2000
64 Correct 25 ms 24668 KB n=2000
65 Correct 24 ms 24668 KB n=2000
66 Correct 24 ms 24668 KB n=2000
67 Correct 25 ms 24668 KB n=2000
68 Correct 24 ms 24668 KB n=2000
69 Correct 23 ms 24668 KB n=2000
70 Correct 23 ms 24668 KB n=2000
71 Correct 23 ms 24668 KB n=2000
72 Correct 22 ms 24668 KB n=2000
73 Correct 24 ms 24668 KB n=2000
74 Correct 27 ms 24668 KB n=1844
75 Correct 22 ms 24668 KB n=2000
76 Correct 24 ms 24668 KB n=2000
77 Correct 23 ms 24668 KB n=2000
78 Correct 24 ms 24668 KB n=2000
79 Correct 27 ms 24668 KB n=2000
80 Correct 25 ms 24668 KB n=2000
81 Correct 26 ms 24668 KB n=2000
82 Correct 26 ms 24668 KB n=2000
83 Correct 24 ms 24736 KB n=2000
84 Correct 23 ms 24736 KB n=2000
85 Correct 25 ms 24736 KB n=2000
86 Correct 30 ms 24736 KB n=2000
87 Correct 30 ms 24736 KB n=2000
88 Correct 26 ms 24736 KB n=2000
89 Correct 28 ms 24736 KB n=2000
90 Correct 25 ms 24736 KB n=2000
91 Correct 24 ms 24736 KB n=2000
92 Correct 969 ms 70744 KB n=200000
93 Correct 1380 ms 76060 KB n=200000
94 Correct 1311 ms 80576 KB n=200000
95 Correct 1067 ms 80576 KB n=200000
96 Correct 1020 ms 80576 KB n=200000
97 Correct 1390 ms 80576 KB n=200000
98 Correct 1006 ms 80576 KB n=200000
99 Correct 1197 ms 80576 KB n=200000
100 Correct 997 ms 80576 KB n=200000
101 Correct 1294 ms 82168 KB n=200000
102 Correct 572 ms 82168 KB n=200000
103 Correct 647 ms 82168 KB n=200000
104 Correct 592 ms 82168 KB n=200000
105 Correct 619 ms 82168 KB n=200000
106 Correct 651 ms 82168 KB n=200000
107 Correct 625 ms 82168 KB n=200000
108 Correct 1080 ms 82168 KB n=200000
109 Correct 1093 ms 82168 KB n=200000
110 Correct 1075 ms 82168 KB n=200000
111 Correct 1086 ms 82168 KB n=200000
112 Correct 1323 ms 82168 KB n=200000
113 Correct 1317 ms 82168 KB n=200000
114 Correct 1083 ms 82168 KB n=200000
115 Correct 1419 ms 82168 KB n=200000
116 Correct 996 ms 82168 KB n=200000
117 Correct 1323 ms 82168 KB n=200000
118 Correct 1322 ms 82168 KB n=200000
119 Correct 939 ms 82168 KB n=200000
120 Correct 1200 ms 82168 KB n=200000
121 Correct 1257 ms 82168 KB n=200000
122 Correct 1212 ms 82516 KB n=200000
123 Correct 554 ms 82516 KB n=200000
124 Correct 332 ms 82516 KB n=25264