oj.uz

Submission #651277

# Submission time Handle Problem Language Result Execution time Memory
651277 2022-10-18T05:47:04 Z becaido Birthday gift (IZhO18_treearray) C++17
100 / 100
 1115 ms 77332 KB 
#pragma GCC optimize("O3")
#pragma GCC target("popcnt")
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define Waimai ios::sync_with_stdio(false),cin.tie(0)
#define FOR(x,a,b) for(int x=a,I=b;x<=I;x++)
#define pb emplace_back
#define F first
#define S second

const int SIZE = 2e5 + 5;
const int H = __lg (SIZE) + 1;

int n, m, q;
vector<int> adj[SIZE];
int h[SIZE], to[SIZE][H + 1];
int a[SIZE];
set<int> s[SIZE], ms[SIZE];

void dfs (int pos, int fa) {
    for (int np : adj[pos]) if (np != fa) {
        h[np] = h[pos] + 1;
        to[np][0] = pos;
        dfs (np, pos);
    }
}

int jump (int pos, int k) {
    int c = 0;
    while (k) {
        if (k & 1) pos = to[pos][c];
        k >>= 1;
        c++;
    }
    return pos;
}

int lca (int a, int b) {
    if (h[a] < h[b]) swap (a, b);
    a = jump (a, h[a] - h[b]);
    if (a == b) return a;
    for (int i = H; i >= 0; i--) if (to[a][i] != to[b][i]) {
        a = to[a][i];
        b = to[b][i];
    }
    return to[a][0];
}

void solve() {
    cin >> n >> m >> q;
    FOR (i, 2, n) {
        int a, b;
        cin >> a >> b;
        adj[a].pb (b);
        adj[b].pb (a);
    }
    h[1] = 1;
    dfs (1, 1);
    FOR (j, 1, H) FOR (i, 1, n) to[i][j] = to[to[i][j - 1]][j - 1];
    FOR (i, 1, m) {
        cin >> a[i];
        s[a[i]].insert (i);
    }
    FOR (i, 2, m) {
        ms[lca (a[i - 1], a[i])].insert (i - 1);
    }
    while (q--) {
        int ty, p, x, l, r, lc;
        cin >> ty;
        if (ty == 1) {
            cin >> p >> x;
            s[a[p]].erase (p);
            if (p > 1) {
                lc = lca (a[p - 1], a[p]);
                ms[lc].erase (p - 1);
            }
            if (p < m) {
                lc = lca (a[p], a[p + 1]);
                ms[lc].erase (p);
            }
            a[p] = x;
            s[a[p]].insert (p);
            if (p > 1) {
                lc = lca (a[p - 1], a[p]);
                ms[lc].insert (p - 1);
            }
            if (p < m) {
                lc = lca (a[p], a[p + 1]);
                ms[lc].insert (p);
            }
        } else {
            cin >> l >> r >> x;
            auto it = s[x].lower_bound (l);
            if (it != s[x].end() && *it <= r) {
                cout << *it << ' ' << *it << '\n';
                continue;
            }
            it = ms[x].lower_bound (l);
            if (it == ms[x].end() || *it + 1 > r) {
                cout << "-1 -1\n";
                continue;
            }
            cout << *it << ' ' << *it + 1 << '\n';
        }
    }
}

int main() {
    Waimai;
    solve();
}

/*
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

3 3 100
1 2
1 3
1 2 3
*/

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23764 KB n=5
2 Correct 14 ms 23812 KB n=100
3 Correct 14 ms 23764 KB n=100
4 Correct 14 ms 23804 KB n=100
5 Correct 15 ms 23764 KB n=100
6 Correct 14 ms 23812 KB n=100
7 Correct 16 ms 23812 KB n=100
8 Correct 13 ms 23764 KB n=100
9 Correct 14 ms 23764 KB n=100
10 Correct 14 ms 23764 KB n=100
11 Correct 14 ms 23764 KB n=100
12 Correct 17 ms 23816 KB n=100
13 Correct 13 ms 23824 KB n=100
14 Correct 13 ms 23764 KB n=100
15 Correct 13 ms 23740 KB n=100
16 Correct 14 ms 23892 KB n=100
17 Correct 14 ms 23816 KB n=100
18 Correct 13 ms 23768 KB n=100
19 Correct 13 ms 23812 KB n=100
20 Correct 12 ms 23812 KB n=100
21 Correct 18 ms 23764 KB n=100
22 Correct 13 ms 23756 KB n=100
23 Correct 14 ms 23764 KB n=100
24 Correct 14 ms 23788 KB n=100
25 Correct 13 ms 23824 KB n=100
26 Correct 13 ms 23764 KB n=12
27 Correct 14 ms 23768 KB n=100

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23764 KB n=5
2 Correct 14 ms 23812 KB n=100
3 Correct 14 ms 23764 KB n=100
4 Correct 14 ms 23804 KB n=100
5 Correct 15 ms 23764 KB n=100
6 Correct 14 ms 23812 KB n=100
7 Correct 16 ms 23812 KB n=100
8 Correct 13 ms 23764 KB n=100
9 Correct 14 ms 23764 KB n=100
10 Correct 14 ms 23764 KB n=100
11 Correct 14 ms 23764 KB n=100
12 Correct 17 ms 23816 KB n=100
13 Correct 13 ms 23824 KB n=100
14 Correct 13 ms 23764 KB n=100
15 Correct 13 ms 23740 KB n=100
16 Correct 14 ms 23892 KB n=100
17 Correct 14 ms 23816 KB n=100
18 Correct 13 ms 23768 KB n=100
19 Correct 13 ms 23812 KB n=100
20 Correct 12 ms 23812 KB n=100
21 Correct 18 ms 23764 KB n=100
22 Correct 13 ms 23756 KB n=100
23 Correct 14 ms 23764 KB n=100
24 Correct 14 ms 23788 KB n=100
25 Correct 13 ms 23824 KB n=100
26 Correct 13 ms 23764 KB n=12
27 Correct 14 ms 23768 KB n=100
28 Correct 14 ms 23836 KB n=500
29 Correct 16 ms 23896 KB n=500
30 Correct 14 ms 23892 KB n=500
31 Correct 14 ms 23892 KB n=500
32 Correct 14 ms 23852 KB n=500
33 Correct 14 ms 23820 KB n=500
34 Correct 16 ms 23892 KB n=500
35 Correct 14 ms 23940 KB n=500
36 Correct 14 ms 23900 KB n=500
37 Correct 17 ms 23892 KB n=500
38 Correct 13 ms 23820 KB n=500
39 Correct 14 ms 23956 KB n=500
40 Correct 14 ms 23892 KB n=500
41 Correct 14 ms 23892 KB n=500
42 Correct 16 ms 23892 KB n=500
43 Correct 14 ms 23844 KB n=500
44 Correct 14 ms 23840 KB n=500
45 Correct 14 ms 23892 KB n=500
46 Correct 15 ms 23960 KB n=500
47 Correct 14 ms 23892 KB n=500
48 Correct 14 ms 23892 KB n=500
49 Correct 14 ms 23948 KB n=500
50 Correct 14 ms 23892 KB n=500
51 Correct 14 ms 23828 KB n=500
52 Correct 15 ms 23948 KB n=500
53 Correct 15 ms 23892 KB n=500
54 Correct 15 ms 23892 KB n=500
55 Correct 13 ms 23900 KB n=278
56 Correct 14 ms 23848 KB n=500
57 Correct 14 ms 23920 KB n=500
58 Correct 14 ms 23892 KB n=500

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23764 KB n=5
2 Correct 14 ms 23812 KB n=100
3 Correct 14 ms 23764 KB n=100
4 Correct 14 ms 23804 KB n=100
5 Correct 15 ms 23764 KB n=100
6 Correct 14 ms 23812 KB n=100
7 Correct 16 ms 23812 KB n=100
8 Correct 13 ms 23764 KB n=100
9 Correct 14 ms 23764 KB n=100
10 Correct 14 ms 23764 KB n=100
11 Correct 14 ms 23764 KB n=100
12 Correct 17 ms 23816 KB n=100
13 Correct 13 ms 23824 KB n=100
14 Correct 13 ms 23764 KB n=100
15 Correct 13 ms 23740 KB n=100
16 Correct 14 ms 23892 KB n=100
17 Correct 14 ms 23816 KB n=100
18 Correct 13 ms 23768 KB n=100
19 Correct 13 ms 23812 KB n=100
20 Correct 12 ms 23812 KB n=100
21 Correct 18 ms 23764 KB n=100
22 Correct 13 ms 23756 KB n=100
23 Correct 14 ms 23764 KB n=100
24 Correct 14 ms 23788 KB n=100
25 Correct 13 ms 23824 KB n=100
26 Correct 13 ms 23764 KB n=12
27 Correct 14 ms 23768 KB n=100
28 Correct 14 ms 23836 KB n=500
29 Correct 16 ms 23896 KB n=500
30 Correct 14 ms 23892 KB n=500
31 Correct 14 ms 23892 KB n=500
32 Correct 14 ms 23852 KB n=500
33 Correct 14 ms 23820 KB n=500
34 Correct 16 ms 23892 KB n=500
35 Correct 14 ms 23940 KB n=500
36 Correct 14 ms 23900 KB n=500
37 Correct 17 ms 23892 KB n=500
38 Correct 13 ms 23820 KB n=500
39 Correct 14 ms 23956 KB n=500
40 Correct 14 ms 23892 KB n=500
41 Correct 14 ms 23892 KB n=500
42 Correct 16 ms 23892 KB n=500
43 Correct 14 ms 23844 KB n=500
44 Correct 14 ms 23840 KB n=500
45 Correct 14 ms 23892 KB n=500
46 Correct 15 ms 23960 KB n=500
47 Correct 14 ms 23892 KB n=500
48 Correct 14 ms 23892 KB n=500
49 Correct 14 ms 23948 KB n=500
50 Correct 14 ms 23892 KB n=500
51 Correct 14 ms 23828 KB n=500
52 Correct 15 ms 23948 KB n=500
53 Correct 15 ms 23892 KB n=500
54 Correct 15 ms 23892 KB n=500
55 Correct 13 ms 23900 KB n=278
56 Correct 14 ms 23848 KB n=500
57 Correct 14 ms 23920 KB n=500
58 Correct 14 ms 23892 KB n=500
59 Correct 16 ms 24284 KB n=2000
60 Correct 15 ms 24280 KB n=2000
61 Correct 17 ms 24276 KB n=2000
62 Correct 17 ms 24312 KB n=2000
63 Correct 18 ms 24276 KB n=2000
64 Correct 18 ms 24260 KB n=2000
65 Correct 17 ms 24276 KB n=2000
66 Correct 18 ms 24276 KB n=2000
67 Correct 18 ms 24212 KB n=2000
68 Correct 17 ms 24288 KB n=2000
69 Correct 17 ms 24212 KB n=2000
70 Correct 19 ms 24204 KB n=2000
71 Correct 17 ms 24312 KB n=2000
72 Correct 16 ms 24236 KB n=2000
73 Correct 15 ms 24248 KB n=2000
74 Correct 18 ms 24204 KB n=1844
75 Correct 17 ms 24208 KB n=2000
76 Correct 17 ms 24200 KB n=2000
77 Correct 16 ms 24268 KB n=2000
78 Correct 19 ms 24204 KB n=2000
79 Correct 21 ms 24284 KB n=2000
80 Correct 16 ms 24260 KB n=2000
81 Correct 17 ms 24268 KB n=2000
82 Correct 16 ms 24260 KB n=2000
83 Correct 22 ms 24248 KB n=2000
84 Correct 19 ms 24276 KB n=2000
85 Correct 16 ms 24276 KB n=2000
86 Correct 17 ms 24288 KB n=2000
87 Correct 17 ms 24184 KB n=2000
88 Correct 17 ms 24276 KB n=2000
89 Correct 17 ms 24276 KB n=2000
90 Correct 17 ms 24276 KB n=2000
91 Correct 16 ms 24276 KB n=2000

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23764 KB n=5
2 Correct 14 ms 23812 KB n=100
3 Correct 14 ms 23764 KB n=100
4 Correct 14 ms 23804 KB n=100
5 Correct 15 ms 23764 KB n=100
6 Correct 14 ms 23812 KB n=100
7 Correct 16 ms 23812 KB n=100
8 Correct 13 ms 23764 KB n=100
9 Correct 14 ms 23764 KB n=100
10 Correct 14 ms 23764 KB n=100
11 Correct 14 ms 23764 KB n=100
12 Correct 17 ms 23816 KB n=100
13 Correct 13 ms 23824 KB n=100
14 Correct 13 ms 23764 KB n=100
15 Correct 13 ms 23740 KB n=100
16 Correct 14 ms 23892 KB n=100
17 Correct 14 ms 23816 KB n=100
18 Correct 13 ms 23768 KB n=100
19 Correct 13 ms 23812 KB n=100
20 Correct 12 ms 23812 KB n=100
21 Correct 18 ms 23764 KB n=100
22 Correct 13 ms 23756 KB n=100
23 Correct 14 ms 23764 KB n=100
24 Correct 14 ms 23788 KB n=100
25 Correct 13 ms 23824 KB n=100
26 Correct 13 ms 23764 KB n=12
27 Correct 14 ms 23768 KB n=100
28 Correct 14 ms 23836 KB n=500
29 Correct 16 ms 23896 KB n=500
30 Correct 14 ms 23892 KB n=500
31 Correct 14 ms 23892 KB n=500
32 Correct 14 ms 23852 KB n=500
33 Correct 14 ms 23820 KB n=500
34 Correct 16 ms 23892 KB n=500
35 Correct 14 ms 23940 KB n=500
36 Correct 14 ms 23900 KB n=500
37 Correct 17 ms 23892 KB n=500
38 Correct 13 ms 23820 KB n=500
39 Correct 14 ms 23956 KB n=500
40 Correct 14 ms 23892 KB n=500
41 Correct 14 ms 23892 KB n=500
42 Correct 16 ms 23892 KB n=500
43 Correct 14 ms 23844 KB n=500
44 Correct 14 ms 23840 KB n=500
45 Correct 14 ms 23892 KB n=500
46 Correct 15 ms 23960 KB n=500
47 Correct 14 ms 23892 KB n=500
48 Correct 14 ms 23892 KB n=500
49 Correct 14 ms 23948 KB n=500
50 Correct 14 ms 23892 KB n=500
51 Correct 14 ms 23828 KB n=500
52 Correct 15 ms 23948 KB n=500
53 Correct 15 ms 23892 KB n=500
54 Correct 15 ms 23892 KB n=500
55 Correct 13 ms 23900 KB n=278
56 Correct 14 ms 23848 KB n=500
57 Correct 14 ms 23920 KB n=500
58 Correct 14 ms 23892 KB n=500
59 Correct 16 ms 24284 KB n=2000
60 Correct 15 ms 24280 KB n=2000
61 Correct 17 ms 24276 KB n=2000
62 Correct 17 ms 24312 KB n=2000
63 Correct 18 ms 24276 KB n=2000
64 Correct 18 ms 24260 KB n=2000
65 Correct 17 ms 24276 KB n=2000
66 Correct 18 ms 24276 KB n=2000
67 Correct 18 ms 24212 KB n=2000
68 Correct 17 ms 24288 KB n=2000
69 Correct 17 ms 24212 KB n=2000
70 Correct 19 ms 24204 KB n=2000
71 Correct 17 ms 24312 KB n=2000
72 Correct 16 ms 24236 KB n=2000
73 Correct 15 ms 24248 KB n=2000
74 Correct 18 ms 24204 KB n=1844
75 Correct 17 ms 24208 KB n=2000
76 Correct 17 ms 24200 KB n=2000
77 Correct 16 ms 24268 KB n=2000
78 Correct 19 ms 24204 KB n=2000
79 Correct 21 ms 24284 KB n=2000
80 Correct 16 ms 24260 KB n=2000
81 Correct 17 ms 24268 KB n=2000
82 Correct 16 ms 24260 KB n=2000
83 Correct 22 ms 24248 KB n=2000
84 Correct 19 ms 24276 KB n=2000
85 Correct 16 ms 24276 KB n=2000
86 Correct 17 ms 24288 KB n=2000
87 Correct 17 ms 24184 KB n=2000
88 Correct 17 ms 24276 KB n=2000
89 Correct 17 ms 24276 KB n=2000
90 Correct 17 ms 24276 KB n=2000
91 Correct 16 ms 24276 KB n=2000
92 Correct 670 ms 71556 KB n=200000
93 Correct 914 ms 73944 KB n=200000
94 Correct 877 ms 76304 KB n=200000
95 Correct 664 ms 71384 KB n=200000
96 Correct 647 ms 71552 KB n=200000
97 Correct 962 ms 73372 KB n=200000
98 Correct 624 ms 71364 KB n=200000
99 Correct 783 ms 71132 KB n=200000
100 Correct 647 ms 71480 KB n=200000
101 Correct 810 ms 77156 KB n=200000
102 Correct 406 ms 72432 KB n=200000
103 Correct 409 ms 72408 KB n=200000
104 Correct 406 ms 72552 KB n=200000
105 Correct 414 ms 72248 KB n=200000
106 Correct 424 ms 72300 KB n=200000
107 Correct 436 ms 72304 KB n=200000
108 Correct 752 ms 71280 KB n=200000
109 Correct 744 ms 71176 KB n=200000
110 Correct 742 ms 71216 KB n=200000
111 Correct 610 ms 71372 KB n=200000
112 Correct 990 ms 76492 KB n=200000
113 Correct 1115 ms 73280 KB n=200000
114 Correct 795 ms 71364 KB n=200000
115 Correct 1002 ms 72048 KB n=200000
116 Correct 632 ms 71308 KB n=200000
117 Correct 831 ms 76844 KB n=200000
118 Correct 944 ms 72420 KB n=200000
119 Correct 624 ms 71352 KB n=200000
120 Correct 766 ms 76900 KB n=200000
121 Correct 792 ms 76936 KB n=200000
122 Correct 806 ms 77332 KB n=200000
123 Correct 411 ms 71932 KB n=200000
124 Correct 189 ms 38224 KB n=25264