oj.uz

Submission #946054

# Submission time Handle Problem Language Result Execution time Memory
946054 2024-03-14T09:52:56 Z atom Birthday gift (IZhO18_treearray) C++17
100 / 100
 596 ms 138068 KB 
#include "bits/stdc++.h"
// @JASPER'S BOILERPLATE
using namespace std;
using ll = long long;

#ifdef JASPER
#include "debug.h"
#else
#define debug(...) 166
#endif

const int N = 2e5 + 5;
const int K = 20;

int n, m, q;
int a[N];
vector <int> adj[N];
// Euler-tour LCA
int tin[N], dep[N], tree[N << 1], lg[N << 1];
pair <int, int> up[K][N << 1];
int timer = 0;

void dfs(int u, int p) {
    tree[++timer] = u;
    tin[u] = timer;
    for (int v : adj[u]) {
        if (v ^ p) {
            dep[v] = dep[u] + 1;
            dfs(v, u);
            tree[++timer] = u;
        }
    }
}
void prepare() {
    dfs(1, 0);

    lg[1] = 0;
    for (int i = 2; i <= timer; ++i) lg[i] = lg[i / 2] + 1;
    for (int i = 1; i <= timer; ++i)
        up[0][i] = {dep[tree[i]], tree[i]};
    for (int k = 1; k < K; ++k) {
        int step = 1 << (k - 1);
        for (int i = 1; i + step <= timer; ++i)
            up[k][i] = min(up[k - 1][i], up[k - 1][i + step]);
    }
}
int lca(int u, int v) {
    int l = tin[u], r = tin[v];
    if (l > r) swap(l, r);
    int k = lg[r - l + 1];
    return min(up[k][l], up[k][r - (1 << k) + 1]).second;
}
// End of LCA

set <int> same[N], diff[N];
signed main() {
    cin.tie(0) -> sync_with_stdio(0);
    
    cin >> n >> m >> q;
    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    prepare();
    for (int i = 1; i <= m; ++i) cin >> a[i]; 

    for (int i = 1; i <= m; ++i)
        same[a[i]].insert(i);
    for (int i = 1; i < m; ++i) {
        int p = lca(a[i], a[i + 1]);
        diff[p].insert(i);
    }

    for (int _q = 1; _q <= q; ++_q) {
        int cmd, x, y, u;
        cin >> cmd >> x >> y;

        // debug(cmd, x, y);
        if (cmd == 1) {
            same[a[x]].erase(x);
            if (2 <= x) {
                int p = lca(a[x], a[x - 1]);
                diff[p].erase(x - 1);
            }
            if (x < m) {
                int p = lca(a[x], a[x + 1]);
                diff[p].erase(x);
            }
            
            a[x] = y;

            same[a[x]].insert(x);
            if (2 <= x) {
                int p = lca(a[x], a[x - 1]);
                diff[p].insert(x - 1);
            }
            if (x < m) {
                int p = lca(a[x], a[x + 1]);
                diff[p].insert(x);
            }
        }
        else {
            cin >> u;   
            // debug(u, ":", same[u], ":", diff[u]);
            pair <int, int> ans = {-1, -1};
            // On the same branch
            auto it_s = same[u].lower_bound(x);
            // On two separated branch
            auto it_d = diff[u].lower_bound(x);
            if (it_s != same[u].end() && *it_s <= y) {
                ans = make_pair(*it_s, *it_s);
            }
            else if (it_d != diff[u].end() && *it_d + 1 <= y) {
                ans = make_pair(*it_d, *it_d + 1);
            }
            cout << ans.first << " " << ans.second << "\n";
        }
    }  
}

Subtask #1
12.0 / 12.0

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

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 39768 KB n=5
2 Correct 9 ms 48132 KB n=100
3 Correct 8 ms 47960 KB n=100
4 Correct 10 ms 47964 KB n=100
5 Correct 8 ms 47964 KB n=100
6 Correct 8 ms 47964 KB n=100
7 Correct 8 ms 47964 KB n=100
8 Correct 8 ms 47960 KB n=100
9 Correct 9 ms 47964 KB n=100
10 Correct 8 ms 47964 KB n=100
11 Correct 8 ms 47960 KB n=100
12 Correct 8 ms 47964 KB n=100
13 Correct 8 ms 47964 KB n=100
14 Correct 8 ms 47960 KB n=100
15 Correct 8 ms 48216 KB n=100
16 Correct 8 ms 47964 KB n=100
17 Correct 8 ms 48192 KB n=100
18 Correct 8 ms 47964 KB n=100
19 Correct 8 ms 47964 KB n=100
20 Correct 10 ms 47964 KB n=100
21 Correct 8 ms 47960 KB n=100
22 Correct 8 ms 47964 KB n=100
23 Correct 9 ms 47964 KB n=100
24 Correct 8 ms 47964 KB n=100
25 Correct 10 ms 48632 KB n=100
26 Correct 7 ms 41820 KB n=12
27 Correct 8 ms 47964 KB n=100
28 Correct 8 ms 52316 KB n=500
29 Correct 8 ms 52240 KB n=500
30 Correct 9 ms 52312 KB n=500
31 Correct 9 ms 52312 KB n=500
32 Correct 9 ms 52312 KB n=500
33 Correct 9 ms 52316 KB n=500
34 Correct 9 ms 52316 KB n=500
35 Correct 10 ms 52316 KB n=500
36 Correct 10 ms 52316 KB n=500
37 Correct 9 ms 52312 KB n=500
38 Correct 9 ms 52312 KB n=500
39 Correct 9 ms 52568 KB n=500
40 Correct 8 ms 52316 KB n=500
41 Correct 10 ms 52312 KB n=500
42 Correct 9 ms 52316 KB n=500
43 Correct 9 ms 52356 KB n=500
44 Correct 9 ms 52312 KB n=500
45 Correct 10 ms 52316 KB n=500
46 Correct 9 ms 52316 KB n=500
47 Correct 9 ms 52312 KB n=500
48 Correct 9 ms 52316 KB n=500
49 Correct 10 ms 52312 KB n=500
50 Correct 9 ms 52316 KB n=500
51 Correct 10 ms 52316 KB n=500
52 Correct 10 ms 52324 KB n=500
53 Correct 9 ms 52120 KB n=500
54 Correct 8 ms 52316 KB n=500
55 Correct 8 ms 52316 KB n=278
56 Correct 9 ms 52248 KB n=500
57 Correct 9 ms 52316 KB n=500
58 Correct 9 ms 52316 KB n=500

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 39768 KB n=5
2 Correct 9 ms 48132 KB n=100
3 Correct 8 ms 47960 KB n=100
4 Correct 10 ms 47964 KB n=100
5 Correct 8 ms 47964 KB n=100
6 Correct 8 ms 47964 KB n=100
7 Correct 8 ms 47964 KB n=100
8 Correct 8 ms 47960 KB n=100
9 Correct 9 ms 47964 KB n=100
10 Correct 8 ms 47964 KB n=100
11 Correct 8 ms 47960 KB n=100
12 Correct 8 ms 47964 KB n=100
13 Correct 8 ms 47964 KB n=100
14 Correct 8 ms 47960 KB n=100
15 Correct 8 ms 48216 KB n=100
16 Correct 8 ms 47964 KB n=100
17 Correct 8 ms 48192 KB n=100
18 Correct 8 ms 47964 KB n=100
19 Correct 8 ms 47964 KB n=100
20 Correct 10 ms 47964 KB n=100
21 Correct 8 ms 47960 KB n=100
22 Correct 8 ms 47964 KB n=100
23 Correct 9 ms 47964 KB n=100
24 Correct 8 ms 47964 KB n=100
25 Correct 10 ms 48632 KB n=100
26 Correct 7 ms 41820 KB n=12
27 Correct 8 ms 47964 KB n=100
28 Correct 8 ms 52316 KB n=500
29 Correct 8 ms 52240 KB n=500
30 Correct 9 ms 52312 KB n=500
31 Correct 9 ms 52312 KB n=500
32 Correct 9 ms 52312 KB n=500
33 Correct 9 ms 52316 KB n=500
34 Correct 9 ms 52316 KB n=500
35 Correct 10 ms 52316 KB n=500
36 Correct 10 ms 52316 KB n=500
37 Correct 9 ms 52312 KB n=500
38 Correct 9 ms 52312 KB n=500
39 Correct 9 ms 52568 KB n=500
40 Correct 8 ms 52316 KB n=500
41 Correct 10 ms 52312 KB n=500
42 Correct 9 ms 52316 KB n=500
43 Correct 9 ms 52356 KB n=500
44 Correct 9 ms 52312 KB n=500
45 Correct 10 ms 52316 KB n=500
46 Correct 9 ms 52316 KB n=500
47 Correct 9 ms 52312 KB n=500
48 Correct 9 ms 52316 KB n=500
49 Correct 10 ms 52312 KB n=500
50 Correct 9 ms 52316 KB n=500
51 Correct 10 ms 52316 KB n=500
52 Correct 10 ms 52324 KB n=500
53 Correct 9 ms 52120 KB n=500
54 Correct 8 ms 52316 KB n=500
55 Correct 8 ms 52316 KB n=278
56 Correct 9 ms 52248 KB n=500
57 Correct 9 ms 52316 KB n=500
58 Correct 9 ms 52316 KB n=500
59 Correct 13 ms 56664 KB n=2000
60 Correct 11 ms 56668 KB n=2000
61 Correct 11 ms 56668 KB n=2000
62 Correct 12 ms 56668 KB n=2000
63 Correct 11 ms 56668 KB n=2000
64 Correct 11 ms 56696 KB n=2000
65 Correct 13 ms 56668 KB n=2000
66 Correct 11 ms 56916 KB n=2000
67 Correct 11 ms 56668 KB n=2000
68 Correct 11 ms 56668 KB n=2000
69 Correct 11 ms 56668 KB n=2000
70 Correct 11 ms 56664 KB n=2000
71 Correct 11 ms 56668 KB n=2000
72 Correct 11 ms 56664 KB n=2000
73 Correct 10 ms 56492 KB n=2000
74 Correct 11 ms 56668 KB n=1844
75 Correct 11 ms 56668 KB n=2000
76 Correct 11 ms 56668 KB n=2000
77 Correct 11 ms 56668 KB n=2000
78 Correct 11 ms 56480 KB n=2000
79 Correct 11 ms 56668 KB n=2000
80 Correct 12 ms 56664 KB n=2000
81 Correct 11 ms 56668 KB n=2000
82 Correct 11 ms 56668 KB n=2000
83 Correct 11 ms 56664 KB n=2000
84 Correct 11 ms 56668 KB n=2000
85 Correct 11 ms 56668 KB n=2000
86 Correct 11 ms 56668 KB n=2000
87 Correct 11 ms 56668 KB n=2000
88 Correct 11 ms 56668 KB n=2000
89 Correct 10 ms 56668 KB n=2000
90 Correct 12 ms 56668 KB n=2000
91 Correct 11 ms 56668 KB n=2000

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 39768 KB n=5
2 Correct 9 ms 48132 KB n=100
3 Correct 8 ms 47960 KB n=100
4 Correct 10 ms 47964 KB n=100
5 Correct 8 ms 47964 KB n=100
6 Correct 8 ms 47964 KB n=100
7 Correct 8 ms 47964 KB n=100
8 Correct 8 ms 47960 KB n=100
9 Correct 9 ms 47964 KB n=100
10 Correct 8 ms 47964 KB n=100
11 Correct 8 ms 47960 KB n=100
12 Correct 8 ms 47964 KB n=100
13 Correct 8 ms 47964 KB n=100
14 Correct 8 ms 47960 KB n=100
15 Correct 8 ms 48216 KB n=100
16 Correct 8 ms 47964 KB n=100
17 Correct 8 ms 48192 KB n=100
18 Correct 8 ms 47964 KB n=100
19 Correct 8 ms 47964 KB n=100
20 Correct 10 ms 47964 KB n=100
21 Correct 8 ms 47960 KB n=100
22 Correct 8 ms 47964 KB n=100
23 Correct 9 ms 47964 KB n=100
24 Correct 8 ms 47964 KB n=100
25 Correct 10 ms 48632 KB n=100
26 Correct 7 ms 41820 KB n=12
27 Correct 8 ms 47964 KB n=100
28 Correct 8 ms 52316 KB n=500
29 Correct 8 ms 52240 KB n=500
30 Correct 9 ms 52312 KB n=500
31 Correct 9 ms 52312 KB n=500
32 Correct 9 ms 52312 KB n=500
33 Correct 9 ms 52316 KB n=500
34 Correct 9 ms 52316 KB n=500
35 Correct 10 ms 52316 KB n=500
36 Correct 10 ms 52316 KB n=500
37 Correct 9 ms 52312 KB n=500
38 Correct 9 ms 52312 KB n=500
39 Correct 9 ms 52568 KB n=500
40 Correct 8 ms 52316 KB n=500
41 Correct 10 ms 52312 KB n=500
42 Correct 9 ms 52316 KB n=500
43 Correct 9 ms 52356 KB n=500
44 Correct 9 ms 52312 KB n=500
45 Correct 10 ms 52316 KB n=500
46 Correct 9 ms 52316 KB n=500
47 Correct 9 ms 52312 KB n=500
48 Correct 9 ms 52316 KB n=500
49 Correct 10 ms 52312 KB n=500
50 Correct 9 ms 52316 KB n=500
51 Correct 10 ms 52316 KB n=500
52 Correct 10 ms 52324 KB n=500
53 Correct 9 ms 52120 KB n=500
54 Correct 8 ms 52316 KB n=500
55 Correct 8 ms 52316 KB n=278
56 Correct 9 ms 52248 KB n=500
57 Correct 9 ms 52316 KB n=500
58 Correct 9 ms 52316 KB n=500
59 Correct 13 ms 56664 KB n=2000
60 Correct 11 ms 56668 KB n=2000
61 Correct 11 ms 56668 KB n=2000
62 Correct 12 ms 56668 KB n=2000
63 Correct 11 ms 56668 KB n=2000
64 Correct 11 ms 56696 KB n=2000
65 Correct 13 ms 56668 KB n=2000
66 Correct 11 ms 56916 KB n=2000
67 Correct 11 ms 56668 KB n=2000
68 Correct 11 ms 56668 KB n=2000
69 Correct 11 ms 56668 KB n=2000
70 Correct 11 ms 56664 KB n=2000
71 Correct 11 ms 56668 KB n=2000
72 Correct 11 ms 56664 KB n=2000
73 Correct 10 ms 56492 KB n=2000
74 Correct 11 ms 56668 KB n=1844
75 Correct 11 ms 56668 KB n=2000
76 Correct 11 ms 56668 KB n=2000
77 Correct 11 ms 56668 KB n=2000
78 Correct 11 ms 56480 KB n=2000
79 Correct 11 ms 56668 KB n=2000
80 Correct 12 ms 56664 KB n=2000
81 Correct 11 ms 56668 KB n=2000
82 Correct 11 ms 56668 KB n=2000
83 Correct 11 ms 56664 KB n=2000
84 Correct 11 ms 56668 KB n=2000
85 Correct 11 ms 56668 KB n=2000
86 Correct 11 ms 56668 KB n=2000
87 Correct 11 ms 56668 KB n=2000
88 Correct 11 ms 56668 KB n=2000
89 Correct 10 ms 56668 KB n=2000
90 Correct 12 ms 56668 KB n=2000
91 Correct 11 ms 56668 KB n=2000
92 Correct 495 ms 125576 KB n=200000
93 Correct 539 ms 131916 KB n=200000
94 Correct 444 ms 136528 KB n=200000
95 Correct 499 ms 125420 KB n=200000
96 Correct 501 ms 125564 KB n=200000
97 Correct 509 ms 130624 KB n=200000
98 Correct 512 ms 125376 KB n=200000
99 Correct 561 ms 125648 KB n=200000
100 Correct 488 ms 125380 KB n=200000
101 Correct 415 ms 138068 KB n=200000
102 Correct 245 ms 126548 KB n=200000
103 Correct 247 ms 126352 KB n=200000
104 Correct 243 ms 126544 KB n=200000
105 Correct 280 ms 126804 KB n=200000
106 Correct 283 ms 126752 KB n=200000
107 Correct 295 ms 126848 KB n=200000
108 Correct 596 ms 125468 KB n=200000
109 Correct 576 ms 125296 KB n=200000
110 Correct 552 ms 125252 KB n=200000
111 Correct 548 ms 124744 KB n=200000
112 Correct 492 ms 136688 KB n=200000
113 Correct 569 ms 130724 KB n=200000
114 Correct 509 ms 124852 KB n=200000
115 Correct 572 ms 127740 KB n=200000
116 Correct 508 ms 125540 KB n=200000
117 Correct 498 ms 137332 KB n=200000
118 Correct 514 ms 129104 KB n=200000
119 Correct 556 ms 125384 KB n=200000
120 Correct 394 ms 137044 KB n=200000
121 Correct 394 ms 136924 KB n=200000
122 Correct 450 ms 137472 KB n=200000
123 Correct 325 ms 126692 KB n=200000
124 Correct 167 ms 83880 KB n=25264