oj.uz

Submission #893801

# Submission time Handle Problem Language Result Execution time Memory
893801 2023-12-27T13:03:37 Z vjudge1 Birthday gift (IZhO18_treearray) C++17
100 / 100
 908 ms 77964 KB 
// 以上帝的名义
// 候选硕士
#include <bits/stdc++.h>

#ifdef local
#include "algo/debug.h"
#else
#define dbg(x...) 0
#endif

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

#define Node int
#define at(i) find_by_order(i)
#define which(x) order_of_key(x)
#define SET tree<Node, null_type,less<Node>, rb_tree_tag,tree_order_statistics_node_update>

using namespace std ;
using ll = long long ;
using ld = long double ;

const int N = 2e5 + 5 ;

int n , m , q, a[N], p[N] ;
vector<int> g[N] ;

int tin[N], tout[N], timer , up[N][20] ;

void dfs(int v, int p) {
    tin[v] = ++timer ;
    up[v][0] = p ;
    for (int i = 1 ; i < 20 ; i++) {
        up[v][i] = up[up[v][i - 1]][i - 1] ;
    }
    for (auto to : g[v]) {
        if (to != p) {
            dfs(to, v) ;
        }
    }
    tout[v] = ++timer ;
}

bool is(int u, int v) {
    return tin[u] <= tin[v] && tout[u] >= tout[v] ;
}

int lca(int u, int v) {
    if (is(u, v)) return u ;
    if (is(v, u)) return v ;
    for (int i = 19 ; ~i ; i--) {
        if (!is(up[u][i], v)) {
            u = up[u][i] ;
        }
    }
    return up[u][0] ;
}

int32_t main() {
    ios::sync_with_stdio(false) ;
    cin.tie(nullptr) ;
    cin >> n >> m >> q ;
    for (int i = 1 ; i < n ; i++) {
        int u , v ; cin >> u >> v;
        g[u].push_back(v) ;
        g[v].push_back(u) ;
    }
    for (int i = 1 ; i <= m ; i++) {
        cin >> a[i] ;
    }
    dfs(1, 1) ;
    set<int> pos[n + 1], difSubtree[n + 1] ;
    for (int i = 1 ; i <= m ; i++) {
        pos[a[i]].insert(i) ;
        if (i < m)
            difSubtree[lca(a[i], a[i + 1])].insert(i) ;
    }
    for (int i = 0 ; i < q ; i++) {
        int cmd ; cin >> cmd ;
        if (cmd == 1) {
            int p, v; cin >> p >> v ;
            int x = a[p] ;
            a[p] = v;
            if (p < m) difSubtree[lca(a[p + 1], x)].erase(p) ;
            if (p > 1) difSubtree[lca(x, a[p - 1])].erase(p - 1) ;
            pos[x].erase(p) ;
            pos[v].insert(p) ;
            if (p < m) difSubtree[lca(a[p + 1], v)].insert(p) ;
            if (p > 1) difSubtree[lca(v, a[p - 1])].insert(p - 1) ;
        } else {
            int l, r, v; cin >> l >> r >> v ;
            auto it = pos[v].lower_bound(l) ;
            if (it != pos[v].end() && *it <= r) {
                cout << *it << ' ' << *it << "\n" ;
            } else {
                auto it = difSubtree[v].lower_bound(l) ;
                if (it != difSubtree[v].end() && *it + 1 <= r) {
                    cout << *it << ' ' << *it + 1 << '\n' ;
                } else {
                    cout << -1 << ' ' << -1 << "\n" ;
                }
            }
        }
    }
    return 0 ;
}

// 希望白银

Subtask #1
12.0 / 12.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
26.0 / 26.0

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

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6492 KB n=5
2 Correct 1 ms 6492 KB n=100
3 Correct 1 ms 6492 KB n=100
4 Correct 1 ms 6492 KB n=100
5 Correct 2 ms 6492 KB n=100
6 Correct 1 ms 6492 KB n=100
7 Correct 1 ms 6488 KB n=100
8 Correct 1 ms 6488 KB n=100
9 Correct 1 ms 6492 KB n=100
10 Correct 1 ms 6488 KB n=100
11 Correct 1 ms 6492 KB n=100
12 Correct 1 ms 6492 KB n=100
13 Correct 1 ms 6492 KB n=100
14 Correct 1 ms 6492 KB n=100
15 Correct 1 ms 6492 KB n=100
16 Correct 2 ms 6492 KB n=100
17 Correct 1 ms 6492 KB n=100
18 Correct 2 ms 6492 KB n=100
19 Correct 2 ms 6492 KB n=100
20 Correct 1 ms 6492 KB n=100
21 Correct 2 ms 6492 KB n=100
22 Correct 1 ms 6492 KB n=100
23 Correct 2 ms 6492 KB n=100
24 Correct 1 ms 6492 KB n=100
25 Correct 1 ms 6624 KB n=100
26 Correct 1 ms 6492 KB n=12
27 Correct 1 ms 6492 KB n=100
28 Correct 2 ms 6748 KB n=500
29 Correct 2 ms 6748 KB n=500
30 Correct 2 ms 6748 KB n=500
31 Correct 2 ms 6748 KB n=500
32 Correct 2 ms 6748 KB n=500
33 Correct 2 ms 6744 KB n=500
34 Correct 2 ms 6748 KB n=500
35 Correct 2 ms 6748 KB n=500
36 Correct 2 ms 6744 KB n=500
37 Correct 2 ms 6748 KB n=500
38 Correct 2 ms 6748 KB n=500
39 Correct 2 ms 6748 KB n=500
40 Correct 3 ms 6748 KB n=500
41 Correct 2 ms 6748 KB n=500
42 Correct 2 ms 6748 KB n=500
43 Correct 2 ms 6748 KB n=500
44 Correct 2 ms 6748 KB n=500
45 Correct 2 ms 6748 KB n=500
46 Correct 2 ms 6748 KB n=500
47 Correct 2 ms 6748 KB n=500
48 Correct 2 ms 6744 KB n=500
49 Correct 2 ms 6748 KB n=500
50 Correct 2 ms 6748 KB n=500
51 Correct 2 ms 6748 KB n=500
52 Correct 2 ms 6744 KB n=500
53 Correct 2 ms 6748 KB n=500
54 Correct 2 ms 6748 KB n=500
55 Correct 2 ms 6492 KB n=278
56 Correct 2 ms 6748 KB n=500
57 Correct 2 ms 6748 KB n=500
58 Correct 2 ms 6744 KB n=500
59 Correct 4 ms 7260 KB n=2000
60 Correct 3 ms 7004 KB n=2000
61 Correct 3 ms 7000 KB n=2000
62 Correct 5 ms 7192 KB n=2000
63 Correct 4 ms 7000 KB n=2000
64 Correct 4 ms 7004 KB n=2000
65 Correct 4 ms 7260 KB n=2000
66 Correct 3 ms 7004 KB n=2000
67 Correct 4 ms 7004 KB n=2000
68 Correct 4 ms 7004 KB n=2000
69 Correct 3 ms 7004 KB n=2000
70 Correct 3 ms 7260 KB n=2000
71 Correct 5 ms 7256 KB n=2000
72 Correct 3 ms 7000 KB n=2000
73 Correct 3 ms 7260 KB n=2000
74 Correct 5 ms 7004 KB n=1844
75 Correct 3 ms 7004 KB n=2000
76 Correct 4 ms 7004 KB n=2000
77 Correct 4 ms 7000 KB n=2000
78 Correct 4 ms 7004 KB n=2000
79 Correct 4 ms 7004 KB n=2000
80 Correct 3 ms 7004 KB n=2000
81 Correct 3 ms 7008 KB n=2000
82 Correct 5 ms 7260 KB n=2000
83 Correct 5 ms 7004 KB n=2000
84 Correct 4 ms 7008 KB n=2000
85 Correct 4 ms 7012 KB n=2000
86 Correct 4 ms 7004 KB n=2000
87 Correct 4 ms 7260 KB n=2000
88 Correct 3 ms 7180 KB n=2000
89 Correct 3 ms 7004 KB n=2000
90 Correct 3 ms 7000 KB n=2000
91 Correct 3 ms 7004 KB n=2000
92 Correct 591 ms 71372 KB n=200000
93 Correct 630 ms 76516 KB n=200000
94 Correct 438 ms 76376 KB n=200000
95 Correct 615 ms 75904 KB n=200000
96 Correct 572 ms 75844 KB n=200000
97 Correct 691 ms 76776 KB n=200000
98 Correct 581 ms 76064 KB n=200000
99 Correct 676 ms 76416 KB n=200000
100 Correct 631 ms 75976 KB n=200000
101 Correct 426 ms 76320 KB n=200000
102 Correct 339 ms 77088 KB n=200000
103 Correct 347 ms 77256 KB n=200000
104 Correct 364 ms 77196 KB n=200000
105 Correct 319 ms 77516 KB n=200000
106 Correct 358 ms 77964 KB n=200000
107 Correct 342 ms 77652 KB n=200000
108 Correct 591 ms 75944 KB n=200000
109 Correct 594 ms 75968 KB n=200000
110 Correct 631 ms 75936 KB n=200000
111 Correct 606 ms 75572 KB n=200000
112 Correct 478 ms 76584 KB n=200000
113 Correct 626 ms 76376 KB n=200000
114 Correct 585 ms 75632 KB n=200000
115 Correct 908 ms 76516 KB n=200000
116 Correct 648 ms 76356 KB n=200000
117 Correct 455 ms 76124 KB n=200000
118 Correct 810 ms 76524 KB n=200000
119 Correct 642 ms 76192 KB n=200000
120 Correct 421 ms 75244 KB n=200000
121 Correct 450 ms 75320 KB n=200000
122 Correct 425 ms 75536 KB n=200000
123 Correct 405 ms 77396 KB n=200000
124 Correct 120 ms 23164 KB n=25264