oj.uz

Submission #1113681

# Submission time Handle Problem Language Result Execution time Memory
1113681 2024-11-17T05:08:15 Z Icelast Birthday gift (IZhO18_treearray) C++17
56 / 100
 780 ms 262144 KB 
#include <iostream>
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn = 2*1e5+5, INF = 4e18+9;
struct Tree{
    int n, root;
    vector<int> depth, head, sz, pa;
    vector<int> f;
    Tree(int n, int root, vector<vector<int>> &adj): n(n), root(root){
        depth.resize(n+1, -1);
        head.resize(n+1);
        sz.resize(n+1, 0);
        pa.resize(n+1, -1);
        auto rootTree = [&](auto rootTree, int u, int p) -> void{
            depth[u] = depth[p]+1;
            pa[u] = p;
            sz[u] = 1;
            for(int v : adj[u]){
                if(v == p) continue;
                rootTree(rootTree, v, u);
                sz[u] += sz[v];
            }
        };
        rootTree(rootTree, root, 0);
        auto decompose = [&](auto decompose, int u, int h) -> void{
            head[u] = h;
            int heavy = -1;
            for(int v : adj[u]){
                if(v == pa[u]) continue;
                if(heavy == -1 || sz[heavy] < sz[v]) heavy = v;
            }
            if(heavy != -1) decompose(decompose, heavy, h);
            for(int v : adj[u]){
                if(v == pa[u] || v == heavy) continue;
                decompose(decompose, v, v);
            }
        };
        decompose(decompose, root, root);
        f = [&]{
            vector<array<int, 2>> first(n+1);
            vector<array<int, 2>> second(n+1);
            function<void(int, int)> dfs0 = [&](int u, int p) {
                first[u] = second[u] = {0, -1};
                for (int v : adj[u]) {
                    if (v == p) {
                        continue;
                    }
                    dfs0(v, u);
                    auto fetch = first[v];
                    fetch[0] += 1;
                    fetch[1] = v;
                    if (fetch > first[u]) {
                        swap(fetch, first[u]);
                    }
                    if (fetch > second[u]) {
                        swap(fetch, second[u]);
                    }
                }
            };
            dfs0(1, 0);

            function<void(int, int)> dfs = [&](int u, int p) {
                for (int v : adj[u]) {
                    if (v == p) {
                        continue;
                    }
                    auto fetch = first[u][1] == v ? second[u] : first[u];
                    fetch[0] += 1;
                    fetch[1] = u;
                    if (fetch > first[v]) {
                        swap(fetch, first[v]);
                    }
                    if (fetch > second[v]) {
                        swap(fetch, second[v]);
                    }
                    dfs(v, u);
                }
            };
            dfs(1, 0);
            vector<int> f(n+1);
            for (int u = 1; u <= n; u++) {
                f[u] = first[u][0];
            }
            return f;
        }();
    };
    int lca(int u, int v){
        for(; head[u] != head[v]; v = pa[head[v]]){
            if(depth[head[u]] > depth[head[v]]) swap(u, v);
        }
        if(depth[u] > depth[v]) swap(u, v);
        return u;
    }
    int dist(int u, int v) {
        return depth[u]+depth[v]-2*depth[lca(u, v)];
    }
};
struct SegmentTree{
    struct Node{
        multiset<pair<int, int>> ms;
    };
    vector<Node> T;
    int n, N;
    SegmentTree(int n) : n(n){
        N = 1;
        while(N < n) N*=2;
        T.resize(N*2+1, Node());
    };
    void upd(int i, pair<int, int> old, pair<int, int> nw){
        auto ie = [&](Node &T, pair<int, int> old, pair<int, int> nw) -> void{
            if(old.first != -1) T.ms.erase(T.ms.find(old));
            T.ms.insert(nw);
        };
        auto upd = [&](auto upd, int node, int low, int high, int i, pair<int, int> old, pair<int, int> nw) -> void{
            ie(T[node], old, nw);
            if(low == high) return;
            int mid = (low+high)/2;
            if(i <= mid){
                upd(upd, node*2, low, mid, i, old, nw);
            }else{
                upd(upd, node*2+1, mid+1, high, i, old, nw);
            }
        };
        upd(upd, 1, 1, N, i, old, nw);
    }
    int query(int l, int r, int v){
        if(l > r) return -1;
        auto query = [&](auto self, int node, int low, int high, int l, int r, int v) -> int{
            if(low > r || l > high) return -1;
            if(low >= l && r >= high){
                auto it = T[node].ms.lower_bound({v, -1});
                if(it == T[node].ms.end()) return -1;
                if((*it).first != v) return -1;
                return (*it).second;
            }
            int mid = (low+high)/2;
            int left = self(self, node*2, low, mid, l, r, v);
            if(left != -1) return left;
            return self(self, node*2+1, mid+1, high, l, r, v);
        };
        return query(query, 1, 1, N, l, r, v);
    }
};
void solve(){
    int n, m, q;
    cin >> n >> m >> q;
    vector<vector<int>> adj(n+1);
    for(int i = 1; i < n; i++){
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    vector<int> a(m+1);
    for(int i = 1; i <= m; i++){
        cin >> a[i];
    }
    SegmentTree T(m+1), T1(m+1);
    Tree Y(n, 1, adj);
    for(int i = 1; i <= m; i++){
        T1.upd(i, {-1, -1}, {a[i], i});
        if(i < m){
            int lca = Y.lca(a[i], a[i+1]);
            T.upd(i, {-1, -1}, {lca, i});
        }
    }
    for(int i = 1; i <= q; i++){
        int t, p, v, l, r;
        cin >> t;
        if(t == 1){
            cin >> p >> v;
            T1.upd(p, {a[p], p}, {v, p});
            pair<int, int> old, nw;
            if(p > 1){
                old = {Y.lca(a[p-1], a[p]), p-1};
                nw = {Y.lca(a[p-1], v), p-1};
                T.upd(p-1, old, nw);
            }
            if(p < m){
                old = {Y.lca(a[p+1], a[p]), p};
                nw = {Y.lca(a[p+1], v), p};
                T.upd(p, old, nw);
            }
            a[p] = v;
        }else{
            cin >> l >> r >> v;
            int one = T1.query(l, r, v);
            int two = T.query(l, r-1, v);
            if(one != -1){
                assert(one >= l && one <= r);
                cout << one << " " << one << "\n";
            }else if(two != -1){
                assert(two >= l && two < r);
                cout << two << " " << two+1 << "\n";
            }else{
                cout << "-1 -1\n";
            }
        }
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    //freopen("main.inp", "r", stdin);
    //freopen("main.out", "w", stdout);
    solve();
}

Subtask #1
12.0 / 12.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB n=5
2 Correct 1 ms 336 KB n=100
3 Correct 1 ms 336 KB n=100
4 Correct 1 ms 560 KB n=100
5 Correct 1 ms 336 KB n=100
6 Correct 1 ms 336 KB n=100
7 Correct 1 ms 336 KB n=100
8 Correct 1 ms 336 KB n=100
9 Correct 1 ms 336 KB n=100
10 Correct 1 ms 336 KB n=100
11 Correct 1 ms 336 KB n=100
12 Correct 1 ms 336 KB n=100
13 Correct 1 ms 336 KB n=100
14 Correct 1 ms 336 KB n=100
15 Correct 1 ms 336 KB n=100
16 Correct 1 ms 336 KB n=100
17 Correct 1 ms 592 KB n=100
18 Correct 1 ms 592 KB n=100
19 Correct 1 ms 336 KB n=100
20 Correct 2 ms 592 KB n=100
21 Correct 1 ms 336 KB n=100
22 Correct 1 ms 512 KB n=100
23 Correct 1 ms 592 KB n=100
24 Correct 2 ms 592 KB n=100
25 Correct 1 ms 592 KB n=100
26 Correct 1 ms 336 KB n=12
27 Correct 1 ms 336 KB n=100
28 Correct 3 ms 848 KB n=500
29 Correct 3 ms 1272 KB n=500
30 Correct 4 ms 1160 KB n=500
31 Correct 4 ms 1104 KB n=500
32 Correct 3 ms 848 KB n=500
33 Correct 4 ms 1104 KB n=500
34 Correct 3 ms 848 KB n=500
35 Correct 3 ms 1104 KB n=500
36 Correct 2 ms 848 KB n=500
37 Correct 2 ms 848 KB n=500
38 Correct 2 ms 848 KB n=500
39 Correct 3 ms 1020 KB n=500
40 Correct 2 ms 848 KB n=500
41 Correct 3 ms 848 KB n=500
42 Correct 3 ms 848 KB n=500
43 Correct 4 ms 848 KB n=500
44 Correct 3 ms 848 KB n=500
45 Correct 3 ms 848 KB n=500
46 Correct 4 ms 1104 KB n=500
47 Correct 4 ms 1104 KB n=500
48 Correct 5 ms 1016 KB n=500
49 Correct 5 ms 1104 KB n=500
50 Correct 4 ms 848 KB n=500
51 Correct 4 ms 1272 KB n=500
52 Correct 3 ms 1104 KB n=500
53 Correct 4 ms 1104 KB n=500
54 Correct 3 ms 1104 KB n=500
55 Correct 2 ms 848 KB n=278
56 Correct 3 ms 1104 KB n=500
57 Correct 5 ms 1104 KB n=500
58 Correct 2 ms 1016 KB n=500
59 Correct 12 ms 3152 KB n=2000
60 Correct 16 ms 3932 KB n=2000
61 Correct 18 ms 3664 KB n=2000
62 Correct 17 ms 3408 KB n=2000
63 Correct 14 ms 3152 KB n=2000
64 Correct 17 ms 3408 KB n=2000
65 Correct 13 ms 3152 KB n=2000
66 Correct 19 ms 3664 KB n=2000
67 Correct 15 ms 3152 KB n=2000
68 Correct 15 ms 3408 KB n=2000
69 Correct 8 ms 3152 KB n=2000
70 Correct 8 ms 3424 KB n=2000
71 Correct 8 ms 3152 KB n=2000
72 Correct 9 ms 3152 KB n=2000
73 Correct 9 ms 3152 KB n=2000
74 Correct 14 ms 3152 KB n=1844
75 Correct 12 ms 3164 KB n=2000
76 Correct 15 ms 3272 KB n=2000
77 Correct 18 ms 3152 KB n=2000
78 Correct 13 ms 3152 KB n=2000
79 Correct 15 ms 3152 KB n=2000
80 Correct 15 ms 3664 KB n=2000
81 Correct 15 ms 3408 KB n=2000
82 Correct 13 ms 3152 KB n=2000
83 Correct 15 ms 3816 KB n=2000
84 Correct 15 ms 3168 KB n=2000
85 Correct 16 ms 3564 KB n=2000
86 Correct 16 ms 3408 KB n=2000
87 Correct 13 ms 3152 KB n=2000
88 Correct 19 ms 4088 KB n=2000
89 Correct 15 ms 3920 KB n=2000
90 Correct 17 ms 4072 KB n=2000
91 Correct 8 ms 3164 KB n=2000

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB n=5
2 Correct 1 ms 336 KB n=100
3 Correct 1 ms 336 KB n=100
4 Correct 1 ms 560 KB n=100
5 Correct 1 ms 336 KB n=100
6 Correct 1 ms 336 KB n=100
7 Correct 1 ms 336 KB n=100
8 Correct 1 ms 336 KB n=100
9 Correct 1 ms 336 KB n=100
10 Correct 1 ms 336 KB n=100
11 Correct 1 ms 336 KB n=100
12 Correct 1 ms 336 KB n=100
13 Correct 1 ms 336 KB n=100
14 Correct 1 ms 336 KB n=100
15 Correct 1 ms 336 KB n=100
16 Correct 1 ms 336 KB n=100
17 Correct 1 ms 592 KB n=100
18 Correct 1 ms 592 KB n=100
19 Correct 1 ms 336 KB n=100
20 Correct 2 ms 592 KB n=100
21 Correct 1 ms 336 KB n=100
22 Correct 1 ms 512 KB n=100
23 Correct 1 ms 592 KB n=100
24 Correct 2 ms 592 KB n=100
25 Correct 1 ms 592 KB n=100
26 Correct 1 ms 336 KB n=12
27 Correct 1 ms 336 KB n=100
28 Correct 3 ms 848 KB n=500
29 Correct 3 ms 1272 KB n=500
30 Correct 4 ms 1160 KB n=500
31 Correct 4 ms 1104 KB n=500
32 Correct 3 ms 848 KB n=500
33 Correct 4 ms 1104 KB n=500
34 Correct 3 ms 848 KB n=500
35 Correct 3 ms 1104 KB n=500
36 Correct 2 ms 848 KB n=500
37 Correct 2 ms 848 KB n=500
38 Correct 2 ms 848 KB n=500
39 Correct 3 ms 1020 KB n=500
40 Correct 2 ms 848 KB n=500
41 Correct 3 ms 848 KB n=500
42 Correct 3 ms 848 KB n=500
43 Correct 4 ms 848 KB n=500
44 Correct 3 ms 848 KB n=500
45 Correct 3 ms 848 KB n=500
46 Correct 4 ms 1104 KB n=500
47 Correct 4 ms 1104 KB n=500
48 Correct 5 ms 1016 KB n=500
49 Correct 5 ms 1104 KB n=500
50 Correct 4 ms 848 KB n=500
51 Correct 4 ms 1272 KB n=500
52 Correct 3 ms 1104 KB n=500
53 Correct 4 ms 1104 KB n=500
54 Correct 3 ms 1104 KB n=500
55 Correct 2 ms 848 KB n=278
56 Correct 3 ms 1104 KB n=500
57 Correct 5 ms 1104 KB n=500
58 Correct 2 ms 1016 KB n=500
59 Correct 12 ms 3152 KB n=2000
60 Correct 16 ms 3932 KB n=2000
61 Correct 18 ms 3664 KB n=2000
62 Correct 17 ms 3408 KB n=2000
63 Correct 14 ms 3152 KB n=2000
64 Correct 17 ms 3408 KB n=2000
65 Correct 13 ms 3152 KB n=2000
66 Correct 19 ms 3664 KB n=2000
67 Correct 15 ms 3152 KB n=2000
68 Correct 15 ms 3408 KB n=2000
69 Correct 8 ms 3152 KB n=2000
70 Correct 8 ms 3424 KB n=2000
71 Correct 8 ms 3152 KB n=2000
72 Correct 9 ms 3152 KB n=2000
73 Correct 9 ms 3152 KB n=2000
74 Correct 14 ms 3152 KB n=1844
75 Correct 12 ms 3164 KB n=2000
76 Correct 15 ms 3272 KB n=2000
77 Correct 18 ms 3152 KB n=2000
78 Correct 13 ms 3152 KB n=2000
79 Correct 15 ms 3152 KB n=2000
80 Correct 15 ms 3664 KB n=2000
81 Correct 15 ms 3408 KB n=2000
82 Correct 13 ms 3152 KB n=2000
83 Correct 15 ms 3816 KB n=2000
84 Correct 15 ms 3168 KB n=2000
85 Correct 16 ms 3564 KB n=2000
86 Correct 16 ms 3408 KB n=2000
87 Correct 13 ms 3152 KB n=2000
88 Correct 19 ms 4088 KB n=2000
89 Correct 15 ms 3920 KB n=2000
90 Correct 17 ms 4072 KB n=2000
91 Correct 8 ms 3164 KB n=2000
92 Runtime error 780 ms 262144 KB Execution killed with signal 9
93 Halted 0 ms 0 KB -