oj.uz

Submission #219810

# Submission time Handle Problem Language Result Execution time Memory
219810 2020-04-06T12:25:29 Z infinite_iq Birthday gift (IZhO18_treearray) C++14
100 / 100
 1369 ms 84216 KB 
#define fast ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#include <bits/stdc++.h>
using namespace std;
#define sqr 400
#define mid (l+r)/2
#define pb push_back
#define ppb pop_back
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound
#define ins insert
#define era erase
#define C continue
#define mem(dp,i) memset(dp,i,sizeof(dp))
#define mset multiset
typedef long long ll;
typedef short int si;
typedef long double ld;
typedef pair<int,int> pi;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pi> vpi;
typedef vector<pll> vpll;
const ll mod=1e9+7;
const ll inf= 4e18;
const ld pai=acos(-1);
int n , m , q;
vi v[200009];
int w[200009] , dp[200009][20] , a[200009];
set<int>s[200009],t[200009];
void dfs(int node,int p){
        dp[node][0]=p;
        w[node]=w[p]+1;
        for ( auto u : v[node]){
                if ( u == p ) C ;
                dfs ( u, node ) ;
        }
}
void build () {
        dfs ( 0,0 );
        for ( int j =1 ;j < 20 ;j ++ ) {
                for ( int i =0 ;i < n ;i ++ ) {
                        dp[i][j] = dp[dp[i][j-1]][j-1];
                }
        }
}
int lca(int a,int b ){
        if ( w[a] < w[b] ) swap ( a , b );
        int l = w[a] - w[b];
        for ( int i =0 ;i <20 ;i ++ ){
                if ( ( l & ( 1<<i ) ) ) a= dp[a][i];
        }
        if ( a == b ) return a ;
        for ( int i = 19 ; i>=0 ;i -- ){
                if ( dp[a][i] != dp[b][i] ) {
                        a=dp[a][i];
                        b=dp[b][i];
                }
        }
        return dp[a][0];
}
int main (){
        fast;
        cin >> n >> m >> q ;
        for ( int i =0 ;i < n-1 ;i ++ ) {
                int a,b;
                cin >> a >> b ;
                a -- , b -- ;
                v[a].pb ( b );
                v[b].pb ( a );
        }
        build();
        for ( int i =0 ;i < m ;i ++ ) {
                cin >> a[i];
                a[i] -- ;
                s[a[i]].ins ( i ) ;
                if ( i ) {
                        t[lca(a[i],a[i-1])].ins(i);
                }
        }
        while ( q -- ) {
                int ty ;
                cin >> ty ;
                if ( ty == 1 ){
                        int pos , id ;
                        cin >> pos >> id ;
                        pos -- , id -- ;
                        s [ a[pos] ] .era(pos);
                        s [ id     ] .ins(pos);
                        if ( pos ) t[lca(a[pos],a[pos-1])].era(pos);
                        if ( pos<m-1) t[lca(a[pos],a[pos+1])].era(pos+1);
                        a[pos]=id;
                        if ( pos ) t[lca(a[pos],a[pos-1])].ins(pos);
                        if ( pos<m-1) t[lca(a[pos],a[pos+1])].ins(pos+1);
                }
                if ( ty == 2 ){
                        int l ,r , node;
                        cin >> l >> r >> node;
                        l -- ,r -- , node -- ;
                        auto it = s[node].lb(l);
                        if ( it != s[node].end() && *it<=r) {
                                cout << *it+1 <<" " << *it+1 << endl;
                                C;
                        }
                        it = t[node].ub(l);
                        if ( it !=t[node].end() && *it<=r ) {
                                cout << *it <<" "<<*it+1<<endl;
                                C;
                        }
                        cout << -1 <<" "<< -1 << endl;

                }
        }
}

Subtask #1
12.0 / 12.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
26.0 / 26.0

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

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23808 KB n=5
2 Correct 17 ms 23808 KB n=100
3 Correct 18 ms 23936 KB n=100
4 Correct 17 ms 23936 KB n=100
5 Correct 18 ms 23808 KB n=100
6 Correct 17 ms 23808 KB n=100
7 Correct 18 ms 23808 KB n=100
8 Correct 17 ms 23808 KB n=100
9 Correct 17 ms 23808 KB n=100
10 Correct 18 ms 23808 KB n=100
11 Correct 18 ms 23808 KB n=100
12 Correct 19 ms 23808 KB n=100
13 Correct 18 ms 23808 KB n=100
14 Correct 18 ms 23808 KB n=100
15 Correct 18 ms 23808 KB n=100
16 Correct 18 ms 23936 KB n=100
17 Correct 17 ms 23808 KB n=100
18 Correct 17 ms 23808 KB n=100
19 Correct 18 ms 23936 KB n=100
20 Correct 17 ms 23808 KB n=100
21 Correct 18 ms 23808 KB n=100
22 Correct 18 ms 23808 KB n=100
23 Correct 18 ms 23808 KB n=100
24 Correct 19 ms 23808 KB n=100
25 Correct 17 ms 23936 KB n=100
26 Correct 19 ms 23808 KB n=12
27 Correct 17 ms 23808 KB n=100
28 Correct 19 ms 23936 KB n=500
29 Correct 21 ms 23936 KB n=500
30 Correct 19 ms 23936 KB n=500
31 Correct 19 ms 23936 KB n=500
32 Correct 19 ms 23936 KB n=500
33 Correct 18 ms 23936 KB n=500
34 Correct 19 ms 23936 KB n=500
35 Correct 19 ms 23936 KB n=500
36 Correct 19 ms 23936 KB n=500
37 Correct 21 ms 23936 KB n=500
38 Correct 19 ms 23936 KB n=500
39 Correct 19 ms 23936 KB n=500
40 Correct 19 ms 23936 KB n=500
41 Correct 19 ms 23936 KB n=500
42 Correct 18 ms 23936 KB n=500
43 Correct 18 ms 23936 KB n=500
44 Correct 19 ms 23936 KB n=500
45 Correct 19 ms 23936 KB n=500
46 Correct 19 ms 24064 KB n=500
47 Correct 19 ms 23936 KB n=500
48 Correct 18 ms 23936 KB n=500
49 Correct 21 ms 23936 KB n=500
50 Correct 19 ms 23936 KB n=500
51 Correct 19 ms 23936 KB n=500
52 Correct 19 ms 23936 KB n=500
53 Correct 19 ms 23936 KB n=500
54 Correct 19 ms 23936 KB n=500
55 Correct 18 ms 23936 KB n=278
56 Correct 19 ms 24064 KB n=500
57 Correct 19 ms 23936 KB n=500
58 Correct 19 ms 23936 KB n=500
59 Correct 24 ms 24320 KB n=2000
60 Correct 23 ms 24456 KB n=2000
61 Correct 23 ms 24448 KB n=2000
62 Correct 24 ms 24320 KB n=2000
63 Correct 23 ms 24320 KB n=2000
64 Correct 23 ms 24320 KB n=2000
65 Correct 23 ms 24320 KB n=2000
66 Correct 23 ms 24448 KB n=2000
67 Correct 23 ms 24320 KB n=2000
68 Correct 24 ms 24320 KB n=2000
69 Correct 24 ms 24320 KB n=2000
70 Correct 24 ms 24320 KB n=2000
71 Correct 23 ms 24320 KB n=2000
72 Correct 24 ms 24320 KB n=2000
73 Correct 23 ms 24320 KB n=2000
74 Correct 22 ms 24320 KB n=1844
75 Correct 24 ms 24320 KB n=2000
76 Correct 23 ms 24320 KB n=2000
77 Correct 24 ms 24320 KB n=2000
78 Correct 23 ms 24320 KB n=2000
79 Correct 23 ms 24320 KB n=2000
80 Correct 23 ms 24448 KB n=2000
81 Correct 23 ms 24448 KB n=2000
82 Correct 23 ms 24192 KB n=2000
83 Correct 23 ms 24440 KB n=2000
84 Correct 23 ms 24312 KB n=2000
85 Correct 23 ms 24320 KB n=2000
86 Correct 23 ms 24320 KB n=2000
87 Correct 23 ms 24320 KB n=2000
88 Correct 22 ms 24448 KB n=2000
89 Correct 24 ms 24448 KB n=2000
90 Correct 22 ms 24448 KB n=2000
91 Correct 24 ms 24320 KB n=2000
92 Correct 1016 ms 74628 KB n=200000
93 Correct 1283 ms 79480 KB n=200000
94 Correct 1282 ms 82872 KB n=200000
95 Correct 992 ms 74604 KB n=200000
96 Correct 952 ms 74604 KB n=200000
97 Correct 1301 ms 78712 KB n=200000
98 Correct 1008 ms 74568 KB n=200000
99 Correct 1216 ms 74784 KB n=200000
100 Correct 1010 ms 74480 KB n=200000
101 Correct 1289 ms 84216 KB n=200000
102 Correct 912 ms 75768 KB n=200000
103 Correct 872 ms 75768 KB n=200000
104 Correct 904 ms 75612 KB n=200000
105 Correct 859 ms 76152 KB n=200000
106 Correct 853 ms 76024 KB n=200000
107 Correct 894 ms 76152 KB n=200000
108 Correct 1092 ms 74488 KB n=200000
109 Correct 1098 ms 74744 KB n=200000
110 Correct 1101 ms 74744 KB n=200000
111 Correct 1016 ms 74100 KB n=200000
112 Correct 1283 ms 83192 KB n=200000
113 Correct 1308 ms 78712 KB n=200000
114 Correct 1016 ms 74024 KB n=200000
115 Correct 1369 ms 76596 KB n=200000
116 Correct 959 ms 74772 KB n=200000
117 Correct 1288 ms 83564 KB n=200000
118 Correct 1329 ms 77724 KB n=200000
119 Correct 953 ms 74600 KB n=200000
120 Correct 1225 ms 83320 KB n=200000
121 Correct 1236 ms 83448 KB n=200000
122 Correct 1250 ms 83576 KB n=200000
123 Correct 918 ms 76024 KB n=200000
124 Correct 307 ms 38716 KB n=25264