oj.uz

Submission #867692

# Submission time Handle Problem Language Result Execution time Memory
867692 2023-10-29T08:26:58 Z sleepntsheep Birthday gift (IZhO18_treearray) C++17
100 / 100
 651 ms 77648 KB 
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <deque>
#include <set>
#include <utility>
#include <array>

using namespace std;
#define ALL(x) x.begin(), x.end()
#define ShinLena cin.tie(nullptr)->sync_with_stdio(false);
using ll = long long;
#define N 200005

int n, m, q, timer, a[N], P[N], J[N], L[N];
int b[N][2];
vector<int> g[N];
set<int> s[N], t[N];

void dfs(int u, int p)
{
    b[u][0] = timer++;
    for (auto v : g[u]) if (v^p) {
        P[v] = u; L[v] = L[u] + 1;
        J[v] = (L[u] - L[J[u]] == L[J[u]] - L[J[J[u]]]) ? J[J[u]]: u;
        dfs(v, u);
    }
    b[u][1] = timer++;
}

int lca(int u, int v)
{
    if (L[u]<L[v])swap(u,v);
    for(;L[u]>L[v];) u=(L[J[u]]>=L[v])?J[u]:P[u];
    for(;u^v;) if (J[u]^J[v])u=J[u],v=J[v]; else u=P[u],v=P[v];
    return u;
}

int main()
{
    ShinLena;
    cin >> n >> m >> q;
    for (int u, v, i = 1; i < n; ++i) cin >> u >> v, g[u].push_back(v), g[v].push_back(u);
    P[1] = J[1] = 1; dfs(1, 1);
    for (int i = 1; i <= m; ++i) cin >> a[i], s[a[i]].insert(i);
    for (int i = 2; i <= m; ++i) t[lca(a[i-1], a[i])].insert(i);

    for (int o, x, y, v; q--;)
    {
        cin >> o >> x >> y;
        if (o == 1) 
        {
            s[a[x]].erase(x);
            if (x>1) t[lca(a[x-1], a[x])].erase(x), t[lca(a[x-1], y)].insert(x);
            if (x<m) t[lca(a[x], a[x+1])].erase(x+1), t[lca(y, a[x+1])].insert(x+1);
            s[y].insert(x);
            a[x] = y;
        }
        else
        {
            cin >> v;
            auto i = s[v].lower_bound(x);
            auto j = t[v].lower_bound(x+1);
            if (i != s[v].end() && *i <= y) cout << *i << ' ' << *i << '\n';
            else if (j != t[v].end() && *j <= y) cout << *j - 1 << ' ' << *j << '\n';
            else cout << "-1 -1\n";
        }
    }

    return 0;
}

Subtask #1
12.0 / 12.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
26.0 / 26.0

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

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 27224 KB n=5
2 Correct 5 ms 27224 KB n=100
3 Correct 5 ms 27228 KB n=100
4 Correct 5 ms 27228 KB n=100
5 Correct 5 ms 27228 KB n=100
6 Correct 5 ms 27224 KB n=100
7 Correct 6 ms 27228 KB n=100
8 Correct 5 ms 27228 KB n=100
9 Correct 5 ms 27228 KB n=100
10 Correct 5 ms 27228 KB n=100
11 Correct 6 ms 27224 KB n=100
12 Correct 5 ms 27228 KB n=100
13 Correct 5 ms 27228 KB n=100
14 Correct 5 ms 27228 KB n=100
15 Correct 5 ms 27224 KB n=100
16 Correct 6 ms 27228 KB n=100
17 Correct 6 ms 27228 KB n=100
18 Correct 5 ms 27228 KB n=100
19 Correct 5 ms 27228 KB n=100
20 Correct 6 ms 27308 KB n=100
21 Correct 6 ms 27228 KB n=100
22 Correct 5 ms 27228 KB n=100
23 Correct 6 ms 27236 KB n=100
24 Correct 5 ms 27332 KB n=100
25 Correct 6 ms 27228 KB n=100
26 Correct 5 ms 27228 KB n=12
27 Correct 5 ms 27308 KB n=100
28 Correct 6 ms 27228 KB n=500
29 Correct 6 ms 27228 KB n=500
30 Correct 6 ms 27228 KB n=500
31 Correct 6 ms 27224 KB n=500
32 Correct 6 ms 27228 KB n=500
33 Correct 6 ms 27228 KB n=500
34 Correct 5 ms 27228 KB n=500
35 Correct 6 ms 27228 KB n=500
36 Correct 7 ms 27320 KB n=500
37 Correct 5 ms 27224 KB n=500
38 Correct 6 ms 27228 KB n=500
39 Correct 7 ms 27228 KB n=500
40 Correct 6 ms 27224 KB n=500
41 Correct 5 ms 27224 KB n=500
42 Correct 6 ms 27224 KB n=500
43 Correct 6 ms 27228 KB n=500
44 Correct 5 ms 27228 KB n=500
45 Correct 6 ms 27228 KB n=500
46 Correct 6 ms 27228 KB n=500
47 Correct 6 ms 27224 KB n=500
48 Correct 5 ms 27228 KB n=500
49 Correct 9 ms 27228 KB n=500
50 Correct 6 ms 27228 KB n=500
51 Correct 6 ms 27320 KB n=500
52 Correct 6 ms 27228 KB n=500
53 Correct 6 ms 27228 KB n=500
54 Correct 5 ms 27228 KB n=500
55 Correct 6 ms 27228 KB n=278
56 Correct 6 ms 27228 KB n=500
57 Correct 6 ms 27480 KB n=500
58 Correct 6 ms 27228 KB n=500
59 Correct 7 ms 27480 KB n=2000
60 Correct 8 ms 27740 KB n=2000
61 Correct 7 ms 27484 KB n=2000
62 Correct 7 ms 27484 KB n=2000
63 Correct 8 ms 27736 KB n=2000
64 Correct 8 ms 27484 KB n=2000
65 Correct 7 ms 27480 KB n=2000
66 Correct 8 ms 27740 KB n=2000
67 Correct 8 ms 27484 KB n=2000
68 Correct 7 ms 27720 KB n=2000
69 Correct 7 ms 27484 KB n=2000
70 Correct 7 ms 27532 KB n=2000
71 Correct 7 ms 27484 KB n=2000
72 Correct 7 ms 27484 KB n=2000
73 Correct 7 ms 27484 KB n=2000
74 Correct 8 ms 27596 KB n=1844
75 Correct 7 ms 27484 KB n=2000
76 Correct 10 ms 27484 KB n=2000
77 Correct 7 ms 27496 KB n=2000
78 Correct 7 ms 27484 KB n=2000
79 Correct 7 ms 27736 KB n=2000
80 Correct 7 ms 27740 KB n=2000
81 Correct 8 ms 27480 KB n=2000
82 Correct 7 ms 27480 KB n=2000
83 Correct 8 ms 27740 KB n=2000
84 Correct 7 ms 27484 KB n=2000
85 Correct 7 ms 27484 KB n=2000
86 Correct 8 ms 27484 KB n=2000
87 Correct 8 ms 27484 KB n=2000
88 Correct 8 ms 27736 KB n=2000
89 Correct 8 ms 27736 KB n=2000
90 Correct 9 ms 27696 KB n=2000
91 Correct 9 ms 27480 KB n=2000
92 Correct 375 ms 62048 KB n=200000
93 Correct 561 ms 69964 KB n=200000
94 Correct 495 ms 75732 KB n=200000
95 Correct 378 ms 61872 KB n=200000
96 Correct 364 ms 61960 KB n=200000
97 Correct 488 ms 68520 KB n=200000
98 Correct 388 ms 61820 KB n=200000
99 Correct 429 ms 62200 KB n=200000
100 Correct 383 ms 62000 KB n=200000
101 Correct 489 ms 77648 KB n=200000
102 Correct 221 ms 63060 KB n=200000
103 Correct 231 ms 63056 KB n=200000
104 Correct 256 ms 63052 KB n=200000
105 Correct 237 ms 63808 KB n=200000
106 Correct 221 ms 63528 KB n=200000
107 Correct 234 ms 63516 KB n=200000
108 Correct 421 ms 62076 KB n=200000
109 Correct 540 ms 61944 KB n=200000
110 Correct 544 ms 61820 KB n=200000
111 Correct 538 ms 61224 KB n=200000
112 Correct 632 ms 76008 KB n=200000
113 Correct 644 ms 68420 KB n=200000
114 Correct 538 ms 61380 KB n=200000
115 Correct 651 ms 64940 KB n=200000
116 Correct 431 ms 62148 KB n=200000
117 Correct 567 ms 76792 KB n=200000
118 Correct 647 ms 66560 KB n=200000
119 Correct 426 ms 62140 KB n=200000
120 Correct 505 ms 76924 KB n=200000
121 Correct 547 ms 76772 KB n=200000
122 Correct 555 ms 77048 KB n=200000
123 Correct 277 ms 63268 KB n=200000
124 Correct 130 ms 40764 KB n=25264