oj.uz

Submission #613647

# Submission time Handle Problem Language Result Execution time Memory
613647 2022-07-30T08:48:19 Z KoD Birthday gift (IZhO18_treearray) C++17
100 / 100
 791 ms 98780 KB 
#include <bits/stdc++.h>

using std::vector;
using std::array;
using std::pair;
using std::tuple;

template <class F> struct fixed : private F {
    explicit fixed(F&& f) : F(std::forward<F>(f)) {}
    template <class... Args> decltype(auto) operator()(Args&&... args) const {
        return F::operator()(*this, std::forward<Args>(args)...);
    }
};

constexpr int LOG = 20;

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int N, M, Q;
    std::cin >> N >> M >> Q;
    vector<vector<int>> graph(N);
    for (int i = 0; i < N - 1; ++i) {
        int a, b;
        std::cin >> a >> b;
        a -= 1;
        b -= 1;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    vector<int> in(N), out(N), depth(N), tour;
    tour.reserve(2 * N - 2);
    fixed([&](auto&& dfs, const int u, const int p) -> void {
        in[u] = (int)tour.size();
        tour.push_back(u);
        for (const int v : graph[u]) {
            if (v != p) {
                depth[v] = depth[u] + 1;
                dfs(v, u);
                tour.push_back(u);
            }
        }
        out[u] = (int)tour.size();
    })(0, -1);

    const auto select = [&](const int i, const int j) {
        return depth[i] < depth[j] ? i : j;
    };
    array<vector<int>, LOG> table = {};
    table[0] = tour;
    for (int d = 0; d + 1 < LOG; ++d) {
        const int n = std::max(0, (int)table[d].size() - (1 << d));
        table[d + 1].resize(n);
        for (int i = 0; i < n; ++i) {
            table[d + 1][i] = select(table[d][i], table[d][i + (1 << d)]);
        }
    }
    const auto lca = [&](const int u, const int v) {
        const int l = std::min(in[u], in[v]);
        const int r = std::max(out[u], out[v]);
        const int t = 31 - __builtin_clz(r - l);
        return select(table[t][l], table[t][r - (1 << t)]);
    };

    vector<std::set<int>> one(N), two(N);
    vector<int> A(M), B(M - 1);
    for (int i = 0; i < M; ++i) {
        std::cin >> A[i];
        A[i] -= 1;
        one[A[i]].insert(i);
    }
    for (int i = 0; i < M - 1; ++i) {
        B[i] = lca(A[i], A[i + 1]);
        two[B[i]].insert(i);
    }
    const auto find = [&](const std::set<int>& set, const int l, const int r) {
        const auto itr = set.lower_bound(l);
        return (itr != set.end() and *itr < r) ? *itr : -1;
    };

    while (Q--) {
        int t;
        std::cin >> t;
        if (t == 1) {
            int p, v;
            std::cin >> p >> v;
            p -= 1;
            v -= 1;
            one[A[p]].erase(p);
            A[p] = v;
            one[A[p]].insert(p);
            if (p > 0) {
                two[B[p - 1]].erase(p - 1);
                B[p - 1] = lca(A[p - 1], A[p]);
                two[B[p - 1]].insert(p - 1);
            }
            if (p + 1 < M) {
                two[B[p]].erase(p);
                B[p] = lca(A[p], A[p + 1]);
                two[B[p]].insert(p);
            }
        } else {
            int l, r, v;
            std::cin >> l >> r >> v;
            l -= 1;
            v -= 1;
            if (const int t = find(one[v], l, r); t != -1) {
                std::cout << t + 1 << ' ' << t + 1 << '\n';
            } else if (const int t = find(two[v], l, r - 1); t != -1) {
                std::cout << t + 1 << ' ' << t + 2 << '\n';
            } else {
                std::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 1 ms 212 KB n=5
2 Correct 1 ms 340 KB n=100
3 Correct 1 ms 340 KB n=100
4 Correct 1 ms 340 KB n=100
5 Correct 1 ms 316 KB n=100
6 Correct 1 ms 340 KB n=100
7 Correct 1 ms 340 KB n=100
8 Correct 1 ms 340 KB n=100
9 Correct 1 ms 340 KB n=100
10 Correct 1 ms 320 KB n=100
11 Correct 0 ms 340 KB n=100
12 Correct 1 ms 340 KB n=100
13 Correct 1 ms 340 KB n=100
14 Correct 1 ms 340 KB n=100
15 Correct 1 ms 340 KB n=100
16 Correct 1 ms 340 KB n=100
17 Correct 0 ms 340 KB n=100
18 Correct 1 ms 340 KB n=100
19 Correct 1 ms 312 KB n=100
20 Correct 1 ms 316 KB n=100
21 Correct 1 ms 340 KB n=100
22 Correct 1 ms 340 KB n=100
23 Correct 1 ms 320 KB n=100
24 Correct 1 ms 340 KB n=100
25 Correct 1 ms 340 KB n=100
26 Correct 1 ms 212 KB n=12
27 Correct 0 ms 340 KB n=100

Subtask #2
18.0 / 18.0

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

Subtask #3
26.0 / 26.0

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

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB n=5
2 Correct 1 ms 340 KB n=100
3 Correct 1 ms 340 KB n=100
4 Correct 1 ms 340 KB n=100
5 Correct 1 ms 316 KB n=100
6 Correct 1 ms 340 KB n=100
7 Correct 1 ms 340 KB n=100
8 Correct 1 ms 340 KB n=100
9 Correct 1 ms 340 KB n=100
10 Correct 1 ms 320 KB n=100
11 Correct 0 ms 340 KB n=100
12 Correct 1 ms 340 KB n=100
13 Correct 1 ms 340 KB n=100
14 Correct 1 ms 340 KB n=100
15 Correct 1 ms 340 KB n=100
16 Correct 1 ms 340 KB n=100
17 Correct 0 ms 340 KB n=100
18 Correct 1 ms 340 KB n=100
19 Correct 1 ms 312 KB n=100
20 Correct 1 ms 316 KB n=100
21 Correct 1 ms 340 KB n=100
22 Correct 1 ms 340 KB n=100
23 Correct 1 ms 320 KB n=100
24 Correct 1 ms 340 KB n=100
25 Correct 1 ms 340 KB n=100
26 Correct 1 ms 212 KB n=12
27 Correct 0 ms 340 KB n=100
28 Correct 2 ms 468 KB n=500
29 Correct 1 ms 468 KB n=500
30 Correct 1 ms 468 KB n=500
31 Correct 1 ms 464 KB n=500
32 Correct 1 ms 468 KB n=500
33 Correct 1 ms 468 KB n=500
34 Correct 1 ms 468 KB n=500
35 Correct 1 ms 468 KB n=500
36 Correct 1 ms 468 KB n=500
37 Correct 1 ms 468 KB n=500
38 Correct 1 ms 468 KB n=500
39 Correct 1 ms 468 KB n=500
40 Correct 1 ms 468 KB n=500
41 Correct 1 ms 452 KB n=500
42 Correct 1 ms 468 KB n=500
43 Correct 1 ms 468 KB n=500
44 Correct 1 ms 468 KB n=500
45 Correct 1 ms 468 KB n=500
46 Correct 1 ms 468 KB n=500
47 Correct 1 ms 468 KB n=500
48 Correct 1 ms 468 KB n=500
49 Correct 1 ms 468 KB n=500
50 Correct 1 ms 464 KB n=500
51 Correct 1 ms 468 KB n=500
52 Correct 1 ms 468 KB n=500
53 Correct 1 ms 468 KB n=500
54 Correct 1 ms 468 KB n=500
55 Correct 1 ms 340 KB n=278
56 Correct 2 ms 468 KB n=500
57 Correct 1 ms 468 KB n=500
58 Correct 1 ms 468 KB n=500
59 Correct 4 ms 1100 KB n=2000
60 Correct 3 ms 1108 KB n=2000
61 Correct 3 ms 1100 KB n=2000
62 Correct 3 ms 1096 KB n=2000
63 Correct 4 ms 1108 KB n=2000
64 Correct 3 ms 1108 KB n=2000
65 Correct 3 ms 1112 KB n=2000
66 Correct 3 ms 1100 KB n=2000
67 Correct 3 ms 980 KB n=2000
68 Correct 3 ms 1108 KB n=2000
69 Correct 3 ms 1108 KB n=2000
70 Correct 3 ms 1100 KB n=2000
71 Correct 3 ms 1092 KB n=2000
72 Correct 3 ms 980 KB n=2000
73 Correct 3 ms 1108 KB n=2000
74 Correct 3 ms 980 KB n=1844
75 Correct 3 ms 980 KB n=2000
76 Correct 3 ms 980 KB n=2000
77 Correct 3 ms 980 KB n=2000
78 Correct 3 ms 980 KB n=2000
79 Correct 3 ms 1100 KB n=2000
80 Correct 3 ms 1108 KB n=2000
81 Correct 4 ms 1108 KB n=2000
82 Correct 4 ms 980 KB n=2000
83 Correct 3 ms 1112 KB n=2000
84 Correct 3 ms 1108 KB n=2000
85 Correct 3 ms 1108 KB n=2000
86 Correct 3 ms 1108 KB n=2000
87 Correct 3 ms 980 KB n=2000
88 Correct 3 ms 1108 KB n=2000
89 Correct 3 ms 1108 KB n=2000
90 Correct 4 ms 1108 KB n=2000
91 Correct 3 ms 1108 KB n=2000
92 Correct 607 ms 90564 KB n=200000
93 Correct 650 ms 94736 KB n=200000
94 Correct 638 ms 97652 KB n=200000
95 Correct 636 ms 90188 KB n=200000
96 Correct 543 ms 90296 KB n=200000
97 Correct 673 ms 93988 KB n=200000
98 Correct 639 ms 90448 KB n=200000
99 Correct 791 ms 90440 KB n=200000
100 Correct 594 ms 90484 KB n=200000
101 Correct 594 ms 98780 KB n=200000
102 Correct 356 ms 91496 KB n=200000
103 Correct 388 ms 91544 KB n=200000
104 Correct 367 ms 91460 KB n=200000
105 Correct 376 ms 91916 KB n=200000
106 Correct 346 ms 91836 KB n=200000
107 Correct 347 ms 91892 KB n=200000
108 Correct 607 ms 90408 KB n=200000
109 Correct 608 ms 90312 KB n=200000
110 Correct 593 ms 90436 KB n=200000
111 Correct 628 ms 89824 KB n=200000
112 Correct 559 ms 97868 KB n=200000
113 Correct 678 ms 93920 KB n=200000
114 Correct 607 ms 89780 KB n=200000
115 Correct 697 ms 92144 KB n=200000
116 Correct 546 ms 90500 KB n=200000
117 Correct 534 ms 98172 KB n=200000
118 Correct 681 ms 92976 KB n=200000
119 Correct 530 ms 90468 KB n=200000
120 Correct 523 ms 97740 KB n=200000
121 Correct 506 ms 97728 KB n=200000
122 Correct 526 ms 98044 KB n=200000
123 Correct 394 ms 91724 KB n=200000
124 Correct 156 ms 19624 KB n=25264