답안 #40603 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
40603	2018-02-05T13:50:29 Z	chonka	Birthday gift (IZhO18_treearray)	C++	100 / 100	1419 ms	82516 KB

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

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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

답안 #40603

Compilation message

Subtask #1 12.0 / 12.0

Subtask #2 18.0 / 18.0

Subtask #3 26.0 / 26.0

Subtask #4 44.0 / 44.0

Subtask #1
12.0 / 12.0

Subtask #2
18.0 / 18.0

Subtask #3
26.0 / 26.0

Subtask #4
44.0 / 44.0