oj.uz

Submission #867694

# Submission time Handle Problem Language Result Execution time Memory
867694 2023-10-29T08:29:22 Z sleepntsheep Birthday gift (IZhO18_treearray) C++17
100 / 100
 525 ms 68676 KB 
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <deque>
#include <set>
#include <utility>
#include <array>
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,tune=native")



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];
vector<int> g[N];
set<int> s[N], t[N];

void dfs(int u, int p)
{
    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);
    }
}

inline 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);
            if (i != s[v].end() && *i <= y) cout << *i << ' ' << *i << '\n';
            else
            {
                auto j = t[v].lower_bound(x+1);
                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 25180 KB n=5
2 Correct 5 ms 25180 KB n=100
3 Correct 5 ms 25180 KB n=100
4 Correct 5 ms 25180 KB n=100
5 Correct 5 ms 25180 KB n=100
6 Correct 5 ms 25276 KB n=100
7 Correct 5 ms 25180 KB n=100
8 Correct 5 ms 25180 KB n=100
9 Correct 5 ms 25180 KB n=100
10 Correct 5 ms 25180 KB n=100
11 Correct 5 ms 25180 KB n=100
12 Correct 5 ms 25180 KB n=100
13 Correct 5 ms 25180 KB n=100
14 Correct 5 ms 25180 KB n=100
15 Correct 6 ms 25176 KB n=100
16 Correct 5 ms 25180 KB n=100
17 Correct 5 ms 25180 KB n=100
18 Correct 5 ms 25224 KB n=100
19 Correct 5 ms 25180 KB n=100
20 Correct 5 ms 25180 KB n=100
21 Correct 5 ms 25180 KB n=100
22 Correct 5 ms 25180 KB n=100
23 Correct 5 ms 25180 KB n=100
24 Correct 5 ms 25180 KB n=100
25 Correct 5 ms 25180 KB n=100
26 Correct 5 ms 25180 KB n=12
27 Correct 7 ms 25232 KB n=100

Subtask #2
18.0 / 18.0

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

Subtask #3
26.0 / 26.0

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

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 25180 KB n=5
2 Correct 5 ms 25180 KB n=100
3 Correct 5 ms 25180 KB n=100
4 Correct 5 ms 25180 KB n=100
5 Correct 5 ms 25180 KB n=100
6 Correct 5 ms 25276 KB n=100
7 Correct 5 ms 25180 KB n=100
8 Correct 5 ms 25180 KB n=100
9 Correct 5 ms 25180 KB n=100
10 Correct 5 ms 25180 KB n=100
11 Correct 5 ms 25180 KB n=100
12 Correct 5 ms 25180 KB n=100
13 Correct 5 ms 25180 KB n=100
14 Correct 5 ms 25180 KB n=100
15 Correct 6 ms 25176 KB n=100
16 Correct 5 ms 25180 KB n=100
17 Correct 5 ms 25180 KB n=100
18 Correct 5 ms 25224 KB n=100
19 Correct 5 ms 25180 KB n=100
20 Correct 5 ms 25180 KB n=100
21 Correct 5 ms 25180 KB n=100
22 Correct 5 ms 25180 KB n=100
23 Correct 5 ms 25180 KB n=100
24 Correct 5 ms 25180 KB n=100
25 Correct 5 ms 25180 KB n=100
26 Correct 5 ms 25180 KB n=12
27 Correct 7 ms 25232 KB n=100
28 Correct 5 ms 25180 KB n=500
29 Correct 5 ms 25180 KB n=500
30 Correct 5 ms 25180 KB n=500
31 Correct 5 ms 25176 KB n=500
32 Correct 5 ms 25180 KB n=500
33 Correct 5 ms 25180 KB n=500
34 Correct 5 ms 25180 KB n=500
35 Correct 5 ms 25180 KB n=500
36 Correct 5 ms 25180 KB n=500
37 Correct 5 ms 25180 KB n=500
38 Correct 6 ms 25180 KB n=500
39 Correct 5 ms 25180 KB n=500
40 Correct 5 ms 25180 KB n=500
41 Correct 5 ms 25180 KB n=500
42 Correct 5 ms 25364 KB n=500
43 Correct 5 ms 25180 KB n=500
44 Correct 5 ms 25180 KB n=500
45 Correct 6 ms 25180 KB n=500
46 Correct 6 ms 25180 KB n=500
47 Correct 5 ms 25180 KB n=500
48 Correct 6 ms 25180 KB n=500
49 Correct 5 ms 25180 KB n=500
50 Correct 5 ms 25216 KB n=500
51 Correct 6 ms 25176 KB n=500
52 Correct 5 ms 25180 KB n=500
53 Correct 5 ms 25180 KB n=500
54 Correct 5 ms 25228 KB n=500
55 Correct 5 ms 25180 KB n=278
56 Correct 5 ms 25176 KB n=500
57 Correct 5 ms 25176 KB n=500
58 Correct 5 ms 25180 KB n=500
59 Correct 7 ms 25436 KB n=2000
60 Correct 7 ms 25688 KB n=2000
61 Correct 7 ms 25436 KB n=2000
62 Correct 7 ms 25436 KB n=2000
63 Correct 7 ms 25548 KB n=2000
64 Correct 7 ms 25436 KB n=2000
65 Correct 7 ms 25436 KB n=2000
66 Correct 7 ms 25688 KB n=2000
67 Correct 7 ms 25432 KB n=2000
68 Correct 7 ms 25432 KB n=2000
69 Correct 6 ms 25688 KB n=2000
70 Correct 6 ms 25432 KB n=2000
71 Correct 6 ms 25436 KB n=2000
72 Correct 6 ms 25436 KB n=2000
73 Correct 6 ms 25432 KB n=2000
74 Correct 6 ms 25436 KB n=1844
75 Correct 6 ms 25476 KB n=2000
76 Correct 7 ms 25436 KB n=2000
77 Correct 7 ms 25436 KB n=2000
78 Correct 7 ms 25436 KB n=2000
79 Correct 7 ms 25432 KB n=2000
80 Correct 7 ms 25436 KB n=2000
81 Correct 7 ms 25436 KB n=2000
82 Correct 7 ms 25436 KB n=2000
83 Correct 7 ms 25436 KB n=2000
84 Correct 6 ms 25436 KB n=2000
85 Correct 7 ms 25468 KB n=2000
86 Correct 7 ms 25436 KB n=2000
87 Correct 7 ms 25436 KB n=2000
88 Correct 7 ms 25692 KB n=2000
89 Correct 9 ms 25692 KB n=2000
90 Correct 7 ms 25692 KB n=2000
91 Correct 7 ms 25636 KB n=2000
92 Correct 366 ms 54096 KB n=200000
93 Correct 475 ms 60756 KB n=200000
94 Correct 478 ms 66384 KB n=200000
95 Correct 366 ms 53824 KB n=200000
96 Correct 338 ms 53776 KB n=200000
97 Correct 503 ms 59384 KB n=200000
98 Correct 351 ms 53960 KB n=200000
99 Correct 434 ms 53236 KB n=200000
100 Correct 356 ms 54036 KB n=200000
101 Correct 481 ms 68676 KB n=200000
102 Correct 213 ms 54868 KB n=200000
103 Correct 217 ms 54760 KB n=200000
104 Correct 216 ms 54684 KB n=200000
105 Correct 226 ms 54608 KB n=200000
106 Correct 218 ms 54640 KB n=200000
107 Correct 234 ms 54604 KB n=200000
108 Correct 402 ms 53688 KB n=200000
109 Correct 440 ms 53756 KB n=200000
110 Correct 402 ms 53840 KB n=200000
111 Correct 416 ms 53688 KB n=200000
112 Correct 465 ms 66644 KB n=200000
113 Correct 481 ms 59216 KB n=200000
114 Correct 376 ms 53696 KB n=200000
115 Correct 514 ms 55636 KB n=200000
116 Correct 353 ms 53700 KB n=200000
117 Correct 463 ms 67344 KB n=200000
118 Correct 525 ms 57580 KB n=200000
119 Correct 348 ms 53744 KB n=200000
120 Correct 463 ms 68536 KB n=200000
121 Correct 436 ms 68340 KB n=200000
122 Correct 463 ms 68608 KB n=200000
123 Correct 226 ms 54100 KB n=200000
124 Correct 113 ms 36944 KB n=25264