oj.uz

답안 #857255

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
857255 2023-10-05T16:48:58 Z dknguyen176 Birthday gift (IZhO18_treearray) C++14
56 / 100
 414 ms 262144 KB 
#include <bits/stdc++.h>
 
#define mp make_pair
 
using namespace std;
 
const int N = 2e5+5;
 
int n, m, q;
vector<int> adj[N];
int a[N];
 
int cnt = 0;
int be[N], en[N], h[N], par[N];
pair<int, int> b[N*2];
 
pair<int, int> rmq[20][N*2];
 
struct LCANode {
    int all, left, right, lpos, rpos;
    multiset<int> pos;
};
LCANode it[N*4];
 
int ans_x, ans_y;
 
void dfs(int u) {
    b[++cnt] = mp(h[u], u);
    be[u] = en[u] = cnt;
 
    for (int &v: adj[u]) if (v != par[u]) {
        par[v] = u;
        h[v] = h[u] + 1;
        dfs(v);
 
        b[++cnt] = mp(h[u], u);
        en[u] = cnt;
    }
}
void build_rmq() {
    for (int i = 1; i <= cnt; ++i) {
        rmq[0][i] = b[i];
    }
    for (int j = 1; (1 << j) <= cnt; ++j) {
        for (int i = 1; i + (1 << j-1) <= cnt; ++i) {
            rmq[j][i] = min(rmq[j-1][i], rmq[j-1][i + (1 << j-1)]);
        }
    }
}
int get_lca(int u, int v) {
    int l = be[u], r = be[v];
    if (l > r) swap(l, r);
    int k = log2(r-l+1);
    auto mi = min(rmq[k][l], rmq[k][r - (1<<k) +1]);
    return mi.second;
}
void build(int k, int l, int r) {
    if (l == r) {
        it[k].all = a[r];
        it[k].pos.insert(be[a[r]]);
        return;
    }
 
    int m = (l + r) >> 1;
    build(k*2, l, m);
    build(k*2+1, m+1, r);
    it[k].all = get_lca(it[k*2].all, it[k*2+1].all);
    for (int i = l; i <= r; ++i) {
        it[k].pos.insert(be[a[i]]);
    }
//    cout << "build " << l << ' ' << r << ' ' << it[k].all << endl;
}
void update(int k, int l, int r, int i, int u, int old_u) {
    if (l == r) {
        it[k].all = u;
        it[k].pos.erase(it[k].pos.find(be[old_u]));
        it[k].pos.insert(be[u]);
        return;
    }
 
    int m = (l + r) >> 1;
    if (i <= m) update(k*2, l, m, i, u, old_u);
    else update(k*2+1, m+1, r, i, u, old_u);
 
    it[k].all = get_lca(it[k*2].all, it[k*2+1].all);
    it[k].pos.erase(it[k].pos.find(be[old_u]));
    it[k].pos.insert(be[u]);
}
LCANode merge_node(LCANode lnode, LCANode rnode, int u) {
    if (lnode.all && rnode.all) {
        int lca = get_lca(lnode.all, rnode.all);
        return LCANode{lca, lca, lca, rnode.lpos, lnode.rpos};
    }
 
    LCANode node;
    node.all = 0;
    node.left = lnode.left;
    node.right = rnode.right;
    node.lpos = lnode.lpos;
    node.rpos = rnode.rpos;
    if (lnode.all && rnode.left) {
        node.left = get_lca(lnode.all, rnode.left);
        node.lpos = rnode.lpos;
    }
    if (rnode.all && lnode.right) {
        node.right = get_lca(rnode.all, lnode.right);
        node.rpos = lnode.rpos;
    }
    if (lnode.right && rnode.left) {
        int lca = get_lca(lnode.right, rnode.left);
        if (lca == u) {
            ans_x = lnode.rpos;
            ans_y = rnode.lpos;
        }
    }
    return node;
}
LCANode get(int k, int l, int r, int ql, int qr, int u) {
    auto tmp = it[k].pos.lower_bound(be[u]);
    if (qr < l || r < ql || tmp == it[k].pos.end() || *tmp > en[u]) {
        return LCANode{0, 0, 0, l-1, r+1};
    }
    if (ql <= l && r <= qr && get_lca(it[k].all, u) == u) {
//        cout << "a " << l << ' ' << r << ' ' << it[k].all << endl;
        int lca = it[k].all;
        if (lca == u) {
            ans_x = l;
            ans_y = r;
        }
        return LCANode{lca, lca, lca, r, l};
    }
    if (l == r) {
        return LCANode{0, 0, 0, l-1, r+1};
    }
 
    int m = (l + r) >> 1;
    LCANode lnode = get(k*2, l, m, ql, qr, u);
    if (ans_x) return LCANode{};
    LCANode rnode = get(k*2+1, m+1, r, ql, qr, u);
    if (ans_x) return LCANode{};
    LCANode node = merge_node(lnode, rnode, u);
//    cout << l << ' ' << r << ' ' << node.all << ' ' << node.left << ' ' << node.right << endl;
//    cout << lnode.all << ' ' << lnode.left << ' ' << lnode.right << endl;
//    cout << rnode.all << ' ' << rnode.left << ' ' << rnode.right << endl;
    return node;
}
int main()
{
//    freopen("a.inp", "r", stdin);
 
    cin >> n >> m >> q;
    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for (int i = 1; i <= m; ++i) {
        cin >> a[i];
    }
 
    dfs(1);
    build_rmq();
 
//    for (int i = 1; i <= cnt; ++i) cout << b[i].second << ' ';
//    cout << endl;
//    cout << "lca " << get_lca(4, 5) << endl;
 
    build(1, 1, m);
 
    for (int i = 1; i <= q; ++i) {
        int t;
        cin >> t;
        if (t == 1) {
            int pos, u;
            cin >> pos >> u;
            update(1, 1, m, pos, u, a[pos]);
            a[pos] = u;
        } else {
            int l, r, u;
            cin >> l >> r >> u;
            ans_x = ans_y = 0;
            get(1, 1, m, l, r, u);
            if (ans_x) cout << ans_x << ' ' << ans_y << '\n';
            else cout << -1 << ' ' << -1 << '\n';
        }
    }
 
    return 0;
}

Compilation message

treearray.cpp: In function 'void build_rmq()':
treearray.cpp:45:36: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   45 |         for (int i = 1; i + (1 << j-1) <= cnt; ++i) {
      |                                   ~^~
treearray.cpp:46:62: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   46 |             rmq[j][i] = min(rmq[j-1][i], rmq[j-1][i + (1 << j-1)]);
      |                                                             ~^~

Subtask #1
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 73560 KB n=5
2 Correct 13 ms 81756 KB n=100
3 Correct 14 ms 81912 KB n=100
4 Correct 14 ms 81756 KB n=100
5 Correct 13 ms 81752 KB n=100
6 Correct 14 ms 81756 KB n=100
7 Correct 14 ms 81756 KB n=100
8 Correct 14 ms 81756 KB n=100
9 Correct 14 ms 81756 KB n=100
10 Correct 14 ms 81756 KB n=100
11 Correct 14 ms 81756 KB n=100
12 Correct 14 ms 81752 KB n=100
13 Correct 13 ms 81756 KB n=100
14 Correct 14 ms 81756 KB n=100
15 Correct 14 ms 81756 KB n=100
16 Correct 14 ms 81792 KB n=100
17 Correct 14 ms 81756 KB n=100
18 Correct 13 ms 81756 KB n=100
19 Correct 13 ms 81752 KB n=100
20 Correct 13 ms 81752 KB n=100
21 Correct 14 ms 81752 KB n=100
22 Correct 13 ms 81756 KB n=100
23 Correct 14 ms 81756 KB n=100
24 Correct 15 ms 81752 KB n=100
25 Correct 14 ms 81756 KB n=100
26 Correct 12 ms 75676 KB n=12
27 Correct 13 ms 81756 KB n=100

Subtask #2
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 73560 KB n=5
2 Correct 13 ms 81756 KB n=100
3 Correct 14 ms 81912 KB n=100
4 Correct 14 ms 81756 KB n=100
5 Correct 13 ms 81752 KB n=100
6 Correct 14 ms 81756 KB n=100
7 Correct 14 ms 81756 KB n=100
8 Correct 14 ms 81756 KB n=100
9 Correct 14 ms 81756 KB n=100
10 Correct 14 ms 81756 KB n=100
11 Correct 14 ms 81756 KB n=100
12 Correct 14 ms 81752 KB n=100
13 Correct 13 ms 81756 KB n=100
14 Correct 14 ms 81756 KB n=100
15 Correct 14 ms 81756 KB n=100
16 Correct 14 ms 81792 KB n=100
17 Correct 14 ms 81756 KB n=100
18 Correct 13 ms 81756 KB n=100
19 Correct 13 ms 81752 KB n=100
20 Correct 13 ms 81752 KB n=100
21 Correct 14 ms 81752 KB n=100
22 Correct 13 ms 81756 KB n=100
23 Correct 14 ms 81756 KB n=100
24 Correct 15 ms 81752 KB n=100
25 Correct 14 ms 81756 KB n=100
26 Correct 12 ms 75676 KB n=12
27 Correct 13 ms 81756 KB n=100
28 Correct 16 ms 86224 KB n=500
29 Correct 17 ms 86108 KB n=500
30 Correct 17 ms 86108 KB n=500
31 Correct 17 ms 86108 KB n=500
32 Correct 16 ms 86108 KB n=500
33 Correct 16 ms 86104 KB n=500
34 Correct 19 ms 86152 KB n=500
35 Correct 17 ms 86108 KB n=500
36 Correct 26 ms 86108 KB n=500
37 Correct 29 ms 86108 KB n=500
38 Correct 26 ms 86108 KB n=500
39 Correct 22 ms 86104 KB n=500
40 Correct 22 ms 86108 KB n=500
41 Correct 21 ms 86108 KB n=500
42 Correct 20 ms 86108 KB n=500
43 Correct 20 ms 86108 KB n=500
44 Correct 21 ms 86108 KB n=500
45 Correct 15 ms 86104 KB n=500
46 Correct 16 ms 86568 KB n=500
47 Correct 17 ms 86108 KB n=500
48 Correct 15 ms 86104 KB n=500
49 Correct 17 ms 86108 KB n=500
50 Correct 16 ms 86140 KB n=500
51 Correct 17 ms 86108 KB n=500
52 Correct 18 ms 86104 KB n=500
53 Correct 16 ms 86108 KB n=500
54 Correct 16 ms 86108 KB n=500
55 Correct 18 ms 86108 KB n=278
56 Correct 16 ms 86108 KB n=500
57 Correct 16 ms 86108 KB n=500
58 Correct 17 ms 86312 KB n=500

Subtask #3
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 73560 KB n=5
2 Correct 13 ms 81756 KB n=100
3 Correct 14 ms 81912 KB n=100
4 Correct 14 ms 81756 KB n=100
5 Correct 13 ms 81752 KB n=100
6 Correct 14 ms 81756 KB n=100
7 Correct 14 ms 81756 KB n=100
8 Correct 14 ms 81756 KB n=100
9 Correct 14 ms 81756 KB n=100
10 Correct 14 ms 81756 KB n=100
11 Correct 14 ms 81756 KB n=100
12 Correct 14 ms 81752 KB n=100
13 Correct 13 ms 81756 KB n=100
14 Correct 14 ms 81756 KB n=100
15 Correct 14 ms 81756 KB n=100
16 Correct 14 ms 81792 KB n=100
17 Correct 14 ms 81756 KB n=100
18 Correct 13 ms 81756 KB n=100
19 Correct 13 ms 81752 KB n=100
20 Correct 13 ms 81752 KB n=100
21 Correct 14 ms 81752 KB n=100
22 Correct 13 ms 81756 KB n=100
23 Correct 14 ms 81756 KB n=100
24 Correct 15 ms 81752 KB n=100
25 Correct 14 ms 81756 KB n=100
26 Correct 12 ms 75676 KB n=12
27 Correct 13 ms 81756 KB n=100
28 Correct 16 ms 86224 KB n=500
29 Correct 17 ms 86108 KB n=500
30 Correct 17 ms 86108 KB n=500
31 Correct 17 ms 86108 KB n=500
32 Correct 16 ms 86108 KB n=500
33 Correct 16 ms 86104 KB n=500
34 Correct 19 ms 86152 KB n=500
35 Correct 17 ms 86108 KB n=500
36 Correct 26 ms 86108 KB n=500
37 Correct 29 ms 86108 KB n=500
38 Correct 26 ms 86108 KB n=500
39 Correct 22 ms 86104 KB n=500
40 Correct 22 ms 86108 KB n=500
41 Correct 21 ms 86108 KB n=500
42 Correct 20 ms 86108 KB n=500
43 Correct 20 ms 86108 KB n=500
44 Correct 21 ms 86108 KB n=500
45 Correct 15 ms 86104 KB n=500
46 Correct 16 ms 86568 KB n=500
47 Correct 17 ms 86108 KB n=500
48 Correct 15 ms 86104 KB n=500
49 Correct 17 ms 86108 KB n=500
50 Correct 16 ms 86140 KB n=500
51 Correct 17 ms 86108 KB n=500
52 Correct 18 ms 86104 KB n=500
53 Correct 16 ms 86108 KB n=500
54 Correct 16 ms 86108 KB n=500
55 Correct 18 ms 86108 KB n=278
56 Correct 16 ms 86108 KB n=500
57 Correct 16 ms 86108 KB n=500
58 Correct 17 ms 86312 KB n=500
59 Correct 27 ms 91484 KB n=2000
60 Correct 49 ms 91484 KB n=2000
61 Correct 48 ms 91316 KB n=2000
62 Correct 44 ms 91228 KB n=2000
63 Correct 23 ms 91224 KB n=2000
64 Correct 45 ms 91196 KB n=2000
65 Correct 23 ms 91224 KB n=2000
66 Correct 51 ms 91228 KB n=2000
67 Correct 28 ms 91480 KB n=2000
68 Correct 52 ms 91228 KB n=2000
69 Correct 222 ms 91584 KB n=2000
70 Correct 206 ms 91228 KB n=2000
71 Correct 206 ms 91228 KB n=2000
72 Correct 133 ms 91324 KB n=2000
73 Correct 120 ms 91224 KB n=2000
74 Correct 22 ms 91224 KB n=1844
75 Correct 122 ms 91324 KB n=2000
76 Correct 112 ms 91328 KB n=2000
77 Correct 112 ms 91224 KB n=2000
78 Correct 116 ms 91224 KB n=2000
79 Correct 23 ms 91224 KB n=2000
80 Correct 48 ms 91228 KB n=2000
81 Correct 41 ms 91224 KB n=2000
82 Correct 23 ms 91228 KB n=2000
83 Correct 45 ms 91228 KB n=2000
84 Correct 24 ms 91480 KB n=2000
85 Correct 38 ms 91224 KB n=2000
86 Correct 34 ms 91224 KB n=2000
87 Correct 23 ms 91228 KB n=2000
88 Correct 25 ms 91480 KB n=2000
89 Correct 25 ms 91484 KB n=2000
90 Correct 23 ms 91484 KB n=2000
91 Correct 22 ms 91196 KB n=2000

Subtask #4
0 / 44.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 73560 KB n=5
2 Correct 13 ms 81756 KB n=100
3 Correct 14 ms 81912 KB n=100
4 Correct 14 ms 81756 KB n=100
5 Correct 13 ms 81752 KB n=100
6 Correct 14 ms 81756 KB n=100
7 Correct 14 ms 81756 KB n=100
8 Correct 14 ms 81756 KB n=100
9 Correct 14 ms 81756 KB n=100
10 Correct 14 ms 81756 KB n=100
11 Correct 14 ms 81756 KB n=100
12 Correct 14 ms 81752 KB n=100
13 Correct 13 ms 81756 KB n=100
14 Correct 14 ms 81756 KB n=100
15 Correct 14 ms 81756 KB n=100
16 Correct 14 ms 81792 KB n=100
17 Correct 14 ms 81756 KB n=100
18 Correct 13 ms 81756 KB n=100
19 Correct 13 ms 81752 KB n=100
20 Correct 13 ms 81752 KB n=100
21 Correct 14 ms 81752 KB n=100
22 Correct 13 ms 81756 KB n=100
23 Correct 14 ms 81756 KB n=100
24 Correct 15 ms 81752 KB n=100
25 Correct 14 ms 81756 KB n=100
26 Correct 12 ms 75676 KB n=12
27 Correct 13 ms 81756 KB n=100
28 Correct 16 ms 86224 KB n=500
29 Correct 17 ms 86108 KB n=500
30 Correct 17 ms 86108 KB n=500
31 Correct 17 ms 86108 KB n=500
32 Correct 16 ms 86108 KB n=500
33 Correct 16 ms 86104 KB n=500
34 Correct 19 ms 86152 KB n=500
35 Correct 17 ms 86108 KB n=500
36 Correct 26 ms 86108 KB n=500
37 Correct 29 ms 86108 KB n=500
38 Correct 26 ms 86108 KB n=500
39 Correct 22 ms 86104 KB n=500
40 Correct 22 ms 86108 KB n=500
41 Correct 21 ms 86108 KB n=500
42 Correct 20 ms 86108 KB n=500
43 Correct 20 ms 86108 KB n=500
44 Correct 21 ms 86108 KB n=500
45 Correct 15 ms 86104 KB n=500
46 Correct 16 ms 86568 KB n=500
47 Correct 17 ms 86108 KB n=500
48 Correct 15 ms 86104 KB n=500
49 Correct 17 ms 86108 KB n=500
50 Correct 16 ms 86140 KB n=500
51 Correct 17 ms 86108 KB n=500
52 Correct 18 ms 86104 KB n=500
53 Correct 16 ms 86108 KB n=500
54 Correct 16 ms 86108 KB n=500
55 Correct 18 ms 86108 KB n=278
56 Correct 16 ms 86108 KB n=500
57 Correct 16 ms 86108 KB n=500
58 Correct 17 ms 86312 KB n=500
59 Correct 27 ms 91484 KB n=2000
60 Correct 49 ms 91484 KB n=2000
61 Correct 48 ms 91316 KB n=2000
62 Correct 44 ms 91228 KB n=2000
63 Correct 23 ms 91224 KB n=2000
64 Correct 45 ms 91196 KB n=2000
65 Correct 23 ms 91224 KB n=2000
66 Correct 51 ms 91228 KB n=2000
67 Correct 28 ms 91480 KB n=2000
68 Correct 52 ms 91228 KB n=2000
69 Correct 222 ms 91584 KB n=2000
70 Correct 206 ms 91228 KB n=2000
71 Correct 206 ms 91228 KB n=2000
72 Correct 133 ms 91324 KB n=2000
73 Correct 120 ms 91224 KB n=2000
74 Correct 22 ms 91224 KB n=1844
75 Correct 122 ms 91324 KB n=2000
76 Correct 112 ms 91328 KB n=2000
77 Correct 112 ms 91224 KB n=2000
78 Correct 116 ms 91224 KB n=2000
79 Correct 23 ms 91224 KB n=2000
80 Correct 48 ms 91228 KB n=2000
81 Correct 41 ms 91224 KB n=2000
82 Correct 23 ms 91228 KB n=2000
83 Correct 45 ms 91228 KB n=2000
84 Correct 24 ms 91480 KB n=2000
85 Correct 38 ms 91224 KB n=2000
86 Correct 34 ms 91224 KB n=2000
87 Correct 23 ms 91228 KB n=2000
88 Correct 25 ms 91480 KB n=2000
89 Correct 25 ms 91484 KB n=2000
90 Correct 23 ms 91484 KB n=2000
91 Correct 22 ms 91196 KB n=2000
92 Runtime error 414 ms 262144 KB Execution killed with signal 9
93 Halted 0 ms 0 KB -