oj.uz

Submission #867693

# Submission time Handle Problem Language Result Execution time Memory
867693 2023-10-29T08:27:25 Z sleepntsheep Birthday gift (IZhO18_treearray) C++17
100 / 100
 574 ms 68776 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];
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);
    }
}

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 25176 KB n=5
2 Correct 6 ms 25288 KB n=100
3 Correct 5 ms 25180 KB n=100
4 Correct 6 ms 25276 KB n=100
5 Correct 6 ms 25180 KB n=100
6 Correct 5 ms 25176 KB n=100
7 Correct 6 ms 25180 KB n=100
8 Correct 5 ms 25180 KB n=100
9 Correct 6 ms 25176 KB n=100
10 Correct 5 ms 25176 KB n=100
11 Correct 5 ms 25272 KB n=100
12 Correct 5 ms 25180 KB n=100
13 Correct 5 ms 25180 KB n=100
14 Correct 6 ms 25180 KB n=100
15 Correct 6 ms 25176 KB n=100
16 Correct 6 ms 25180 KB n=100
17 Correct 5 ms 25176 KB n=100
18 Correct 6 ms 25180 KB n=100
19 Correct 5 ms 25180 KB n=100
20 Correct 5 ms 25036 KB n=100
21 Correct 5 ms 25180 KB n=100
22 Correct 5 ms 25180 KB n=100
23 Correct 6 ms 25180 KB n=100
24 Correct 6 ms 25180 KB n=100
25 Correct 5 ms 25180 KB n=100
26 Correct 5 ms 25176 KB n=12
27 Correct 5 ms 25180 KB n=100

Subtask #2
18.0 / 18.0

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

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 25176 KB n=5
2 Correct 6 ms 25288 KB n=100
3 Correct 5 ms 25180 KB n=100
4 Correct 6 ms 25276 KB n=100
5 Correct 6 ms 25180 KB n=100
6 Correct 5 ms 25176 KB n=100
7 Correct 6 ms 25180 KB n=100
8 Correct 5 ms 25180 KB n=100
9 Correct 6 ms 25176 KB n=100
10 Correct 5 ms 25176 KB n=100
11 Correct 5 ms 25272 KB n=100
12 Correct 5 ms 25180 KB n=100
13 Correct 5 ms 25180 KB n=100
14 Correct 6 ms 25180 KB n=100
15 Correct 6 ms 25176 KB n=100
16 Correct 6 ms 25180 KB n=100
17 Correct 5 ms 25176 KB n=100
18 Correct 6 ms 25180 KB n=100
19 Correct 5 ms 25180 KB n=100
20 Correct 5 ms 25036 KB n=100
21 Correct 5 ms 25180 KB n=100
22 Correct 5 ms 25180 KB n=100
23 Correct 6 ms 25180 KB n=100
24 Correct 6 ms 25180 KB n=100
25 Correct 5 ms 25180 KB n=100
26 Correct 5 ms 25176 KB n=12
27 Correct 5 ms 25180 KB n=100
28 Correct 5 ms 25180 KB n=500
29 Correct 6 ms 25268 KB n=500
30 Correct 5 ms 25180 KB n=500
31 Correct 6 ms 25360 KB n=500
32 Correct 6 ms 25180 KB n=500
33 Correct 6 ms 25180 KB n=500
34 Correct 6 ms 25180 KB n=500
35 Correct 5 ms 25180 KB n=500
36 Correct 5 ms 25216 KB n=500
37 Correct 5 ms 25284 KB n=500
38 Correct 5 ms 25176 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 6 ms 25180 KB n=500
43 Correct 6 ms 25180 KB n=500
44 Correct 6 ms 25180 KB n=500
45 Correct 5 ms 25180 KB n=500
46 Correct 5 ms 25176 KB n=500
47 Correct 6 ms 25180 KB n=500
48 Correct 5 ms 25180 KB n=500
49 Correct 5 ms 25180 KB n=500
50 Correct 5 ms 25176 KB n=500
51 Correct 6 ms 25180 KB n=500
52 Correct 5 ms 25180 KB n=500
53 Correct 6 ms 25436 KB n=500
54 Correct 6 ms 25184 KB n=500
55 Correct 5 ms 25180 KB n=278
56 Correct 6 ms 25180 KB n=500
57 Correct 5 ms 25180 KB n=500
58 Correct 5 ms 25180 KB n=500
59 Correct 9 ms 25436 KB n=2000
60 Correct 7 ms 25692 KB n=2000
61 Correct 9 ms 25436 KB n=2000
62 Correct 7 ms 25436 KB n=2000
63 Correct 7 ms 25436 KB n=2000
64 Correct 7 ms 25432 KB n=2000
65 Correct 9 ms 25436 KB n=2000
66 Correct 7 ms 25436 KB n=2000
67 Correct 9 ms 25432 KB n=2000
68 Correct 8 ms 25432 KB n=2000
69 Correct 7 ms 25552 KB n=2000
70 Correct 8 ms 25432 KB n=2000
71 Correct 7 ms 25432 KB n=2000
72 Correct 8 ms 25436 KB n=2000
73 Correct 6 ms 25436 KB n=2000
74 Correct 7 ms 25432 KB n=1844
75 Correct 6 ms 25436 KB n=2000
76 Correct 7 ms 25436 KB n=2000
77 Correct 9 ms 25600 KB n=2000
78 Correct 7 ms 25432 KB n=2000
79 Correct 8 ms 25436 KB n=2000
80 Correct 7 ms 25436 KB n=2000
81 Correct 7 ms 25436 KB n=2000
82 Correct 7 ms 25688 KB n=2000
83 Correct 9 ms 25432 KB n=2000
84 Correct 7 ms 25436 KB n=2000
85 Correct 9 ms 25436 KB n=2000
86 Correct 9 ms 25432 KB n=2000
87 Correct 8 ms 25688 KB n=2000
88 Correct 9 ms 25688 KB n=2000
89 Correct 7 ms 25688 KB n=2000
90 Correct 7 ms 25692 KB n=2000
91 Correct 7 ms 25436 KB n=2000
92 Correct 479 ms 54112 KB n=200000
93 Correct 556 ms 60944 KB n=200000
94 Correct 574 ms 66384 KB n=200000
95 Correct 468 ms 53700 KB n=200000
96 Correct 400 ms 53884 KB n=200000
97 Correct 559 ms 59772 KB n=200000
98 Correct 433 ms 54260 KB n=200000
99 Correct 502 ms 53216 KB n=200000
100 Correct 429 ms 53952 KB n=200000
101 Correct 527 ms 68776 KB n=200000
102 Correct 265 ms 54868 KB n=200000
103 Correct 220 ms 54760 KB n=200000
104 Correct 229 ms 54804 KB n=200000
105 Correct 226 ms 55124 KB n=200000
106 Correct 246 ms 54452 KB n=200000
107 Correct 238 ms 54668 KB n=200000
108 Correct 449 ms 53588 KB n=200000
109 Correct 512 ms 53588 KB n=200000
110 Correct 567 ms 53616 KB n=200000
111 Correct 522 ms 53896 KB n=200000
112 Correct 515 ms 66776 KB n=200000
113 Correct 532 ms 59216 KB n=200000
114 Correct 422 ms 53704 KB n=200000
115 Correct 567 ms 55792 KB n=200000
116 Correct 402 ms 53692 KB n=200000
117 Correct 475 ms 67472 KB n=200000
118 Correct 552 ms 57348 KB n=200000
119 Correct 336 ms 53696 KB n=200000
120 Correct 459 ms 68284 KB n=200000
121 Correct 437 ms 68248 KB n=200000
122 Correct 431 ms 68576 KB n=200000
123 Correct 210 ms 54096 KB n=200000
124 Correct 154 ms 36884 KB n=25264