oj.uz

Submission #651249

# Submission time Handle Problem Language Result Execution time Memory
651249 2022-10-18T03:36:53 Z Astrayt Birthday gift (IZhO18_treearray) C++17
30 / 100
 4000 ms 25372 KB 
#include <bits/stdc++.h>
#define pb push_back
#define lc (p << 1)
#define rc ((p << 1) | 1)
#define mid ((l + r) >> 1)
using namespace std;
array<int, 1 << 20> P, dep;
array<int, 1 << 20> S;
array<array<int, 20>, 1 << 20> A;
array<vector<int>, 1 << 20> T;
void DFS(int u, int pre, int d){
    dep[u] = d;
    for(int v : T[u]){
        if(v == pre) continue;
        A[v][0] = u;
        DFS(v, u, d + 1);
    }
}
void DABO(int n){
    for(int j = 1; j < 20; j++){
        for(int i = 1; i <= n; i++){
            A[i][j] = A[A[i][j - 1]][j - 1];
        }
    }
}
int LCA(int a, int b){
    if(!a || !b) return a ? a : b;
    if(dep[a] >= dep[b]) swap(a, b);
    for(int i = 19; i >= 0; i--){
        if(dep[A[b][i]] >= dep[a]) b = A[b][i];
    }
    if(a == b) return b;
    for(int i = 19; i >= 0; i--){
        if(A[a][i] != A[b][i]) a = A[a][i], b = A[b][i];
    }
    return A[a][0];
}
signed main(){
    cin.tie(0), cout.tie(0), ios::sync_with_stdio(0);
    int n, m, q, u, v, t, l, r, p, can;
    cin >> n >> m >> q;
    for(int i = 1; i < n; i++){
        cin >> u >> v;
        T[u].pb(v), T[v].pb(u);
    }
    DFS(1, 0, 0);
    DABO(n);
    for(int i = 1; i <= m; i++){
        cin >> P[i];
    }
    while(q--){
        cin >> t >> l >> r;
        if(t == 1){
            P[l] = r;
        }else{
            can = 0;
            cin >> v;
            for(int i = l; i <= r; i++){
                p = 0;
                if(can) break;
                for(int j = i; j <= r; j++){
                    p = LCA(p, P[j]);
                    if(p == v){
                        cout << i << " " << j << "\n";
                        can = 1;
                        break;
                    }
                    if(dep[p] <= dep[v]) break;
                }
            }
            if(!can) cout << "-1 -1\n";
        }
    }
    return 0;
}
/*
5 4 4
1 2
3 1
3 4
5 3
4 5 2 3
2 1 3 1
1 3 5
2 3 4 5
2 1 3 1
*/

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 24916 KB n=5
2 Correct 17 ms 24924 KB n=100
3 Correct 15 ms 24916 KB n=100
4 Correct 14 ms 24916 KB n=100
5 Correct 13 ms 24916 KB n=100
6 Correct 14 ms 24916 KB n=100
7 Correct 14 ms 24956 KB n=100
8 Correct 14 ms 24916 KB n=100
9 Correct 17 ms 24980 KB n=100
10 Correct 16 ms 24972 KB n=100
11 Correct 17 ms 24912 KB n=100
12 Correct 19 ms 24916 KB n=100
13 Correct 13 ms 24944 KB n=100
14 Correct 13 ms 24916 KB n=100
15 Correct 13 ms 24916 KB n=100
16 Correct 16 ms 24936 KB n=100
17 Correct 18 ms 24888 KB n=100
18 Correct 17 ms 24932 KB n=100
19 Correct 14 ms 24940 KB n=100
20 Correct 14 ms 24900 KB n=100
21 Correct 15 ms 24872 KB n=100
22 Correct 15 ms 24916 KB n=100
23 Correct 25 ms 24968 KB n=100
24 Correct 24 ms 24928 KB n=100
25 Correct 17 ms 24916 KB n=100
26 Correct 16 ms 24916 KB n=12
27 Correct 16 ms 24952 KB n=100

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 24916 KB n=5
2 Correct 17 ms 24924 KB n=100
3 Correct 15 ms 24916 KB n=100
4 Correct 14 ms 24916 KB n=100
5 Correct 13 ms 24916 KB n=100
6 Correct 14 ms 24916 KB n=100
7 Correct 14 ms 24956 KB n=100
8 Correct 14 ms 24916 KB n=100
9 Correct 17 ms 24980 KB n=100
10 Correct 16 ms 24972 KB n=100
11 Correct 17 ms 24912 KB n=100
12 Correct 19 ms 24916 KB n=100
13 Correct 13 ms 24944 KB n=100
14 Correct 13 ms 24916 KB n=100
15 Correct 13 ms 24916 KB n=100
16 Correct 16 ms 24936 KB n=100
17 Correct 18 ms 24888 KB n=100
18 Correct 17 ms 24932 KB n=100
19 Correct 14 ms 24940 KB n=100
20 Correct 14 ms 24900 KB n=100
21 Correct 15 ms 24872 KB n=100
22 Correct 15 ms 24916 KB n=100
23 Correct 25 ms 24968 KB n=100
24 Correct 24 ms 24928 KB n=100
25 Correct 17 ms 24916 KB n=100
26 Correct 16 ms 24916 KB n=12
27 Correct 16 ms 24952 KB n=100
28 Correct 15 ms 24956 KB n=500
29 Correct 26 ms 25044 KB n=500
30 Correct 26 ms 25040 KB n=500
31 Correct 35 ms 24928 KB n=500
32 Correct 14 ms 24976 KB n=500
33 Correct 29 ms 24916 KB n=500
34 Correct 18 ms 24964 KB n=500
35 Correct 23 ms 25048 KB n=500
36 Correct 36 ms 25044 KB n=500
37 Correct 35 ms 24916 KB n=500
38 Correct 40 ms 25016 KB n=500
39 Correct 26 ms 25036 KB n=500
40 Correct 24 ms 24964 KB n=500
41 Correct 26 ms 24964 KB n=500
42 Correct 32 ms 25016 KB n=500
43 Correct 29 ms 24928 KB n=500
44 Correct 26 ms 25044 KB n=500
45 Correct 14 ms 24916 KB n=500
46 Correct 26 ms 24964 KB n=500
47 Correct 22 ms 25028 KB n=500
48 Correct 14 ms 24964 KB n=500
49 Correct 20 ms 25044 KB n=500
50 Correct 14 ms 24916 KB n=500
51 Correct 26 ms 25040 KB n=500
52 Correct 31 ms 25044 KB n=500
53 Correct 28 ms 24960 KB n=500
54 Correct 263 ms 25024 KB n=500
55 Correct 16 ms 24952 KB n=278
56 Correct 2442 ms 25024 KB n=500
57 Correct 2547 ms 25044 KB n=500
58 Correct 21 ms 25020 KB n=500

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 24916 KB n=5
2 Correct 17 ms 24924 KB n=100
3 Correct 15 ms 24916 KB n=100
4 Correct 14 ms 24916 KB n=100
5 Correct 13 ms 24916 KB n=100
6 Correct 14 ms 24916 KB n=100
7 Correct 14 ms 24956 KB n=100
8 Correct 14 ms 24916 KB n=100
9 Correct 17 ms 24980 KB n=100
10 Correct 16 ms 24972 KB n=100
11 Correct 17 ms 24912 KB n=100
12 Correct 19 ms 24916 KB n=100
13 Correct 13 ms 24944 KB n=100
14 Correct 13 ms 24916 KB n=100
15 Correct 13 ms 24916 KB n=100
16 Correct 16 ms 24936 KB n=100
17 Correct 18 ms 24888 KB n=100
18 Correct 17 ms 24932 KB n=100
19 Correct 14 ms 24940 KB n=100
20 Correct 14 ms 24900 KB n=100
21 Correct 15 ms 24872 KB n=100
22 Correct 15 ms 24916 KB n=100
23 Correct 25 ms 24968 KB n=100
24 Correct 24 ms 24928 KB n=100
25 Correct 17 ms 24916 KB n=100
26 Correct 16 ms 24916 KB n=12
27 Correct 16 ms 24952 KB n=100
28 Correct 15 ms 24956 KB n=500
29 Correct 26 ms 25044 KB n=500
30 Correct 26 ms 25040 KB n=500
31 Correct 35 ms 24928 KB n=500
32 Correct 14 ms 24976 KB n=500
33 Correct 29 ms 24916 KB n=500
34 Correct 18 ms 24964 KB n=500
35 Correct 23 ms 25048 KB n=500
36 Correct 36 ms 25044 KB n=500
37 Correct 35 ms 24916 KB n=500
38 Correct 40 ms 25016 KB n=500
39 Correct 26 ms 25036 KB n=500
40 Correct 24 ms 24964 KB n=500
41 Correct 26 ms 24964 KB n=500
42 Correct 32 ms 25016 KB n=500
43 Correct 29 ms 24928 KB n=500
44 Correct 26 ms 25044 KB n=500
45 Correct 14 ms 24916 KB n=500
46 Correct 26 ms 24964 KB n=500
47 Correct 22 ms 25028 KB n=500
48 Correct 14 ms 24964 KB n=500
49 Correct 20 ms 25044 KB n=500
50 Correct 14 ms 24916 KB n=500
51 Correct 26 ms 25040 KB n=500
52 Correct 31 ms 25044 KB n=500
53 Correct 28 ms 24960 KB n=500
54 Correct 263 ms 25024 KB n=500
55 Correct 16 ms 24952 KB n=278
56 Correct 2442 ms 25024 KB n=500
57 Correct 2547 ms 25044 KB n=500
58 Correct 21 ms 25020 KB n=500
59 Correct 17 ms 25220 KB n=2000
60 Correct 286 ms 25296 KB n=2000
61 Correct 257 ms 25296 KB n=2000
62 Correct 380 ms 25256 KB n=2000
63 Correct 17 ms 25172 KB n=2000
64 Correct 292 ms 25260 KB n=2000
65 Correct 16 ms 25188 KB n=2000
66 Correct 406 ms 25196 KB n=2000
67 Correct 20 ms 25172 KB n=2000
68 Correct 331 ms 25164 KB n=2000
69 Correct 376 ms 25372 KB n=2000
70 Correct 395 ms 25240 KB n=2000
71 Correct 384 ms 25252 KB n=2000
72 Correct 223 ms 25244 KB n=2000
73 Correct 201 ms 25172 KB n=2000
74 Correct 16 ms 25288 KB n=1844
75 Correct 229 ms 25260 KB n=2000
76 Correct 255 ms 25240 KB n=2000
77 Correct 265 ms 25236 KB n=2000
78 Correct 274 ms 25244 KB n=2000
79 Correct 19 ms 25248 KB n=2000
80 Correct 205 ms 25280 KB n=2000
81 Correct 235 ms 25260 KB n=2000
82 Correct 16 ms 25172 KB n=2000
83 Correct 202 ms 25272 KB n=2000
84 Correct 40 ms 25272 KB n=2000
85 Correct 547 ms 25260 KB n=2000
86 Correct 244 ms 25296 KB n=2000
87 Correct 42 ms 25296 KB n=2000
88 Execution timed out 4064 ms 25300 KB Time limit exceeded
89 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 24916 KB n=5
2 Correct 17 ms 24924 KB n=100
3 Correct 15 ms 24916 KB n=100
4 Correct 14 ms 24916 KB n=100
5 Correct 13 ms 24916 KB n=100
6 Correct 14 ms 24916 KB n=100
7 Correct 14 ms 24956 KB n=100
8 Correct 14 ms 24916 KB n=100
9 Correct 17 ms 24980 KB n=100
10 Correct 16 ms 24972 KB n=100
11 Correct 17 ms 24912 KB n=100
12 Correct 19 ms 24916 KB n=100
13 Correct 13 ms 24944 KB n=100
14 Correct 13 ms 24916 KB n=100
15 Correct 13 ms 24916 KB n=100
16 Correct 16 ms 24936 KB n=100
17 Correct 18 ms 24888 KB n=100
18 Correct 17 ms 24932 KB n=100
19 Correct 14 ms 24940 KB n=100
20 Correct 14 ms 24900 KB n=100
21 Correct 15 ms 24872 KB n=100
22 Correct 15 ms 24916 KB n=100
23 Correct 25 ms 24968 KB n=100
24 Correct 24 ms 24928 KB n=100
25 Correct 17 ms 24916 KB n=100
26 Correct 16 ms 24916 KB n=12
27 Correct 16 ms 24952 KB n=100
28 Correct 15 ms 24956 KB n=500
29 Correct 26 ms 25044 KB n=500
30 Correct 26 ms 25040 KB n=500
31 Correct 35 ms 24928 KB n=500
32 Correct 14 ms 24976 KB n=500
33 Correct 29 ms 24916 KB n=500
34 Correct 18 ms 24964 KB n=500
35 Correct 23 ms 25048 KB n=500
36 Correct 36 ms 25044 KB n=500
37 Correct 35 ms 24916 KB n=500
38 Correct 40 ms 25016 KB n=500
39 Correct 26 ms 25036 KB n=500
40 Correct 24 ms 24964 KB n=500
41 Correct 26 ms 24964 KB n=500
42 Correct 32 ms 25016 KB n=500
43 Correct 29 ms 24928 KB n=500
44 Correct 26 ms 25044 KB n=500
45 Correct 14 ms 24916 KB n=500
46 Correct 26 ms 24964 KB n=500
47 Correct 22 ms 25028 KB n=500
48 Correct 14 ms 24964 KB n=500
49 Correct 20 ms 25044 KB n=500
50 Correct 14 ms 24916 KB n=500
51 Correct 26 ms 25040 KB n=500
52 Correct 31 ms 25044 KB n=500
53 Correct 28 ms 24960 KB n=500
54 Correct 263 ms 25024 KB n=500
55 Correct 16 ms 24952 KB n=278
56 Correct 2442 ms 25024 KB n=500
57 Correct 2547 ms 25044 KB n=500
58 Correct 21 ms 25020 KB n=500
59 Correct 17 ms 25220 KB n=2000
60 Correct 286 ms 25296 KB n=2000
61 Correct 257 ms 25296 KB n=2000
62 Correct 380 ms 25256 KB n=2000
63 Correct 17 ms 25172 KB n=2000
64 Correct 292 ms 25260 KB n=2000
65 Correct 16 ms 25188 KB n=2000
66 Correct 406 ms 25196 KB n=2000
67 Correct 20 ms 25172 KB n=2000
68 Correct 331 ms 25164 KB n=2000
69 Correct 376 ms 25372 KB n=2000
70 Correct 395 ms 25240 KB n=2000
71 Correct 384 ms 25252 KB n=2000
72 Correct 223 ms 25244 KB n=2000
73 Correct 201 ms 25172 KB n=2000
74 Correct 16 ms 25288 KB n=1844
75 Correct 229 ms 25260 KB n=2000
76 Correct 255 ms 25240 KB n=2000
77 Correct 265 ms 25236 KB n=2000
78 Correct 274 ms 25244 KB n=2000
79 Correct 19 ms 25248 KB n=2000
80 Correct 205 ms 25280 KB n=2000
81 Correct 235 ms 25260 KB n=2000
82 Correct 16 ms 25172 KB n=2000
83 Correct 202 ms 25272 KB n=2000
84 Correct 40 ms 25272 KB n=2000
85 Correct 547 ms 25260 KB n=2000
86 Correct 244 ms 25296 KB n=2000
87 Correct 42 ms 25296 KB n=2000
88 Execution timed out 4064 ms 25300 KB Time limit exceeded
89 Halted 0 ms 0 KB -