oj.uz

Submission #339032

# Submission time Handle Problem Language Result Execution time Memory
339032 2020-12-24T12:05:44 Z saarang123 Birthday gift (IZhO18_treearray) C++14
100 / 100
 1876 ms 87788 KB 
#include <bits/stdc++.h>
using namespace std;

struct LCA {
    int n,i,j,t;
    vector<vector<int>> g, par;
    vector<int> dt;
    void init(int x) {
        n = x; t = ceil(log2(n));
        dt.resize(n + 2);
        g = vector<vector<int>>(n + 2, vector<int>());
        par = vector<vector<int>>(n + 2, vector<int>(t + 2));
    }
    void add(int v, int u) { g[v].push_back(u); g[u].push_back(v); }
    void build(int v = 1, int p = 1, int d = 0) {
        dt[v] = d; par[v][0] = p;
        for(i=1; i<t; i++) {
            if(par[par[v][i-1]][i-1] != -1) par[v][i] = par[par[v][i-1]][i-1];
        }
        for(int u: g[v]) {
            if(u != p) build(u, v, d+1);
        }
    }
    int kth(int a, int diff) {
        for(i = 0; i < t; i++) {
            if(diff & (1 << i))
                a = par[a][i];
        }
        return a;
    }
    int lca(int a, int b) {
        if(dt[a] < dt[b]) swap(a, b);
        a = kth(a, dt[a] - dt[b]);
        if(a == b) return a;
        for(i = t - 1; i >= 0; i--) {
            if(par[a][i] != par[b][i]) { a = par[a][i]; b = par[b][i]; }
        }
        return par[a][0];
    }
    int dist(int a, int b) { return dt[a] + dt[b] - 2 * dt[lca(a,b)]; }
};

signed main() {
    std::ios::sync_with_stdio(0);
    std::cout.tie(0);
    std::cin.tie(0);
    //freopen("input.txt", "r", stdin);
    int n, m, q;
    cin >> n >> m >> q;
    LCA tree;
    tree.init(n);
    for(int u, v, _ = 1; _ < n; _++) {
        cin >> u >> v;
        tree.add(u, v);
    }
    tree.build();
    vector<int> a(m + 1);
    vector<set<int>> one(n + 1), two(n + 1);
    for(int i = 1; i <= m; i++) {
        cin >> a[i];
        one[a[i]].insert(i);
    }
    for(int i = 2; i <= m; i++) {
        two[tree.lca(a[i], a[i - 1])].insert(i - 1);
    }
    while(q--) {
        int tp; cin >> tp;
        if(tp == 1) {
            int x, v; cin >> x >> v;
            one[a[x]].erase(x);
            if(x < m) two[tree.lca(a[x], a[x + 1])].erase(x);
            if(x > 1) two[tree.lca(a[x], a[x - 1])].erase(x - 1);
            a[x] = v;
            one[a[x]].insert(x);
            if(x < m) two[tree.lca(a[x], a[x + 1])].insert(x);
            if(x > 1) two[tree.lca(a[x], a[x - 1])].insert(x - 1);
        }
        else {
            int l, r, v;
            cin >> l >> r >> v;
            int id = 0;
            if(!one[v].empty()) {
                auto x = one[v].lower_bound(l);
                if(x != one[v].end()) id = *x;
                if(l <= id && id <= r) {
                    cout << id << ' ' << id << endl;
                    continue;
                }
            }
            if(!two[v].empty()) {
                auto x = two[v].lower_bound(l);
                if(x != two[v].end()) id = *x;
                if(l <= id && id + 1 <= r) {
                    cout << id << ' ' << id + 1 << endl;
                    continue;
                }
            }
            cout << -1 << ' ' << -1 << endl;
        }
    }
    return 0;
}

Subtask #1
12.0 / 12.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
26.0 / 26.0

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

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB n=5
2 Correct 1 ms 364 KB n=100
3 Correct 1 ms 364 KB n=100
4 Correct 1 ms 364 KB n=100
5 Correct 1 ms 364 KB n=100
6 Correct 1 ms 364 KB n=100
7 Correct 1 ms 364 KB n=100
8 Correct 1 ms 364 KB n=100
9 Correct 1 ms 364 KB n=100
10 Correct 1 ms 364 KB n=100
11 Correct 1 ms 364 KB n=100
12 Correct 1 ms 364 KB n=100
13 Correct 1 ms 364 KB n=100
14 Correct 1 ms 364 KB n=100
15 Correct 1 ms 364 KB n=100
16 Correct 1 ms 364 KB n=100
17 Correct 1 ms 364 KB n=100
18 Correct 1 ms 364 KB n=100
19 Correct 1 ms 364 KB n=100
20 Correct 1 ms 364 KB n=100
21 Correct 1 ms 364 KB n=100
22 Correct 1 ms 364 KB n=100
23 Correct 1 ms 364 KB n=100
24 Correct 1 ms 364 KB n=100
25 Correct 1 ms 364 KB n=100
26 Correct 1 ms 364 KB n=12
27 Correct 1 ms 364 KB n=100
28 Correct 3 ms 492 KB n=500
29 Correct 2 ms 492 KB n=500
30 Correct 2 ms 492 KB n=500
31 Correct 2 ms 492 KB n=500
32 Correct 2 ms 492 KB n=500
33 Correct 2 ms 492 KB n=500
34 Correct 2 ms 492 KB n=500
35 Correct 2 ms 492 KB n=500
36 Correct 2 ms 492 KB n=500
37 Correct 2 ms 492 KB n=500
38 Correct 2 ms 492 KB n=500
39 Correct 2 ms 492 KB n=500
40 Correct 2 ms 492 KB n=500
41 Correct 2 ms 492 KB n=500
42 Correct 2 ms 492 KB n=500
43 Correct 2 ms 492 KB n=500
44 Correct 2 ms 492 KB n=500
45 Correct 2 ms 492 KB n=500
46 Correct 2 ms 492 KB n=500
47 Correct 2 ms 492 KB n=500
48 Correct 2 ms 492 KB n=500
49 Correct 2 ms 492 KB n=500
50 Correct 2 ms 492 KB n=500
51 Correct 2 ms 492 KB n=500
52 Correct 2 ms 492 KB n=500
53 Correct 2 ms 492 KB n=500
54 Correct 2 ms 492 KB n=500
55 Correct 1 ms 492 KB n=278
56 Correct 2 ms 492 KB n=500
57 Correct 2 ms 492 KB n=500
58 Correct 2 ms 492 KB n=500
59 Correct 7 ms 1004 KB n=2000
60 Correct 6 ms 1132 KB n=2000
61 Correct 6 ms 1132 KB n=2000
62 Correct 7 ms 1004 KB n=2000
63 Correct 7 ms 1004 KB n=2000
64 Correct 7 ms 1024 KB n=2000
65 Correct 6 ms 1004 KB n=2000
66 Correct 6 ms 1132 KB n=2000
67 Correct 7 ms 1004 KB n=2000
68 Correct 7 ms 1132 KB n=2000
69 Correct 8 ms 1004 KB n=2000
70 Correct 8 ms 1004 KB n=2000
71 Correct 8 ms 1004 KB n=2000
72 Correct 8 ms 1004 KB n=2000
73 Correct 8 ms 1004 KB n=2000
74 Correct 6 ms 1004 KB n=1844
75 Correct 8 ms 1004 KB n=2000
76 Correct 7 ms 1004 KB n=2000
77 Correct 7 ms 1004 KB n=2000
78 Correct 7 ms 1004 KB n=2000
79 Correct 6 ms 1004 KB n=2000
80 Correct 7 ms 1260 KB n=2000
81 Correct 7 ms 1004 KB n=2000
82 Correct 8 ms 1004 KB n=2000
83 Correct 7 ms 1132 KB n=2000
84 Correct 6 ms 1004 KB n=2000
85 Correct 7 ms 1004 KB n=2000
86 Correct 7 ms 1132 KB n=2000
87 Correct 6 ms 1004 KB n=2000
88 Correct 6 ms 1132 KB n=2000
89 Correct 6 ms 1132 KB n=2000
90 Correct 6 ms 1132 KB n=2000
91 Correct 8 ms 1004 KB n=2000
92 Correct 1164 ms 76048 KB n=200000
93 Correct 1801 ms 81260 KB n=200000
94 Correct 1770 ms 85648 KB n=200000
95 Correct 1147 ms 75872 KB n=200000
96 Correct 1094 ms 75872 KB n=200000
97 Correct 1821 ms 80364 KB n=200000
98 Correct 1128 ms 76128 KB n=200000
99 Correct 1398 ms 75452 KB n=200000
100 Correct 1143 ms 76132 KB n=200000
101 Correct 1729 ms 87276 KB n=200000
102 Correct 986 ms 76908 KB n=200000
103 Correct 1006 ms 76908 KB n=200000
104 Correct 994 ms 76952 KB n=200000
105 Correct 994 ms 76788 KB n=200000
106 Correct 1002 ms 76684 KB n=200000
107 Correct 1014 ms 76556 KB n=200000
108 Correct 1321 ms 75628 KB n=200000
109 Correct 1329 ms 75628 KB n=200000
110 Correct 1332 ms 75884 KB n=200000
111 Correct 1149 ms 76000 KB n=200000
112 Correct 1746 ms 86208 KB n=200000
113 Correct 1828 ms 80332 KB n=200000
114 Correct 1115 ms 75872 KB n=200000
115 Correct 1876 ms 77420 KB n=200000
116 Correct 1108 ms 75684 KB n=200000
117 Correct 1713 ms 86636 KB n=200000
118 Correct 1804 ms 78700 KB n=200000
119 Correct 1081 ms 75796 KB n=200000
120 Correct 1695 ms 87148 KB n=200000
121 Correct 1692 ms 87292 KB n=200000
122 Correct 1661 ms 87788 KB n=200000
123 Correct 1016 ms 76268 KB n=200000
124 Correct 377 ms 17260 KB n=25264