oj.uz

Submission #957774

# Submission time Handle Problem Language Result Execution time Memory
957774 2024-04-04T10:06:41 Z Ghetto Magic Tree (CEOI19_magictree) C++17
20 / 100
 1542 ms 457112 KB 
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
const int MAX_N = 1e5 + 5, MAX_K = 1e5 + 5;

int n, m, k;
vector<int> children[MAX_N];
int t[MAX_N];
lint val[MAX_N]; // val = 0 => not fruit

struct Node {
    lint ans, lazy_add, lazy_set;
};
vector<Node> segtree[MAX_N];
int n_nodes[MAX_N];
vector<int> lo[MAX_N], hi[MAX_N], l_child[MAX_N], r_child[MAX_N];
void init() {
    for (int i = 1; i <= n; i++) {
        n_nodes[i] = 1;
        segtree[i] = {{0, 0, 0}, {0, 0, 0}};
        l_child[i] = r_child[i] = {0, 0};
        lo[i] = {0, 1};
        hi[i] = {0, MAX_K};
    }
}
void expand(int tree, int u) {
    if (l_child[tree][u]) return;

    l_child[tree][u] = ++n_nodes[tree];
    r_child[tree][u] = ++n_nodes[tree];

    for (int i = 1; i <= 2; i++) {
        segtree[tree].push_back({0, 0, 0});
        lo[tree].push_back(0);
        hi[tree].push_back(0);
        l_child[tree].push_back(0);
        r_child[tree].push_back(0);
    }
    
    int mid = (lo[tree][u] + hi[tree][u]) / 2;
    lo[tree][l_child[tree][u]] = lo[tree][u];
    hi[tree][l_child[tree][u]] = mid;
    lo[tree][r_child[tree][u]] = mid + 1;
    hi[tree][r_child[tree][u]] = hi[tree][u];
}
void propogate(int tree, int u) {
    if (segtree[tree][u].lazy_set != 0) {
        segtree[tree][l_child[tree][u]].ans = segtree[tree][u].lazy_set;
        segtree[tree][r_child[tree][u]].ans = segtree[tree][u].lazy_set;
        segtree[tree][l_child[tree][u]].lazy_set = segtree[tree][u].lazy_set;
        segtree[tree][r_child[tree][u]].lazy_set = segtree[tree][u].lazy_set;
    }
    if (segtree[tree][u].lazy_add != 0) {
        segtree[tree][l_child[tree][u]].ans += segtree[tree][u].lazy_add;    
        segtree[tree][r_child[tree][u]].ans += segtree[tree][u].lazy_add;
        segtree[tree][l_child[tree][u]].lazy_add += segtree[tree][u].lazy_add;    
        segtree[tree][r_child[tree][u]].lazy_add += segtree[tree][u].lazy_add;
    }
    segtree[tree][u].lazy_set = segtree[tree][u].lazy_add = 0;
}
void set_update(int tree, int l, int r, lint x, int u = 1) {
    if (l <= lo[tree][u] && hi[tree][u] <= r) {
        // cout << lo[tree][u] << " " << hi[tree][u] << " " << u << ": " << x << endl;
        segtree[tree][u].ans = x;
        segtree[tree][u].lazy_set = x;
        segtree[tree][u].lazy_add = 0;
        return;
    } 

    expand(tree, u);
    propogate(tree, u);
    int mid = (lo[tree][u] + hi[tree][u]) / 2;
    if (l <= mid) set_update(tree, l, r, x, l_child[tree][u]);
    if (r > mid) set_update(tree, l, r, x, r_child[tree][u]);
    segtree[tree][u].ans = max(segtree[tree][l_child[tree][u]].ans, segtree[tree][r_child[tree][u]].ans);
}
void add_update(int tree, int l, int r, lint x, int u = 1) {
    if (l <= lo[tree][u] && hi[tree][u] <= r) {
        segtree[tree][u].ans += x;
        segtree[tree][u].lazy_add += x;
        return;
    } 

    expand(tree, u);
    propogate(tree, u);
    int mid = (lo[tree][u] + hi[tree][u]) / 2;
    if (l <= mid) add_update(tree, l, r, x, l_child[tree][u]);
    if (r > mid) add_update(tree, l, r, x, r_child[tree][u]);
    segtree[tree][u].ans = max(segtree[tree][l_child[tree][u]].ans, segtree[tree][r_child[tree][u]].ans);
}
lint query(int tree, int i, int u = 1) {
    // cout << "QUERY " << lo[tree][u] << " " << hi[tree][u] << " " << u << ": " << segtree[tree][u].ans << endl;
    if (lo[tree][u] == hi[tree][u]) {
        // cout << "QUERY" << lo[tree][u] << " " << segtree[tree][u].ans << endl;
        return segtree[tree][u].ans;
    }

    expand(tree, u);
    propogate(tree, u);
    int mid = (lo[tree][u] + hi[tree][u]) / 2;
    if (i <= mid) return query(tree, i, l_child[tree][u]);
    else return query(tree, i, r_child[tree][u]);
}
int walk(int tree, int l, int r, lint x, int u = 1) { // First i >= x
    if (segtree[tree][u].ans < x) return r + 1;
    if (lo[tree][u] > r || hi[tree][u] < l) return r + 1;
    if (lo[tree][u] == hi[tree][u]) return lo[tree][u];

    expand(tree, u);
    propogate(tree, u);
    int l_resp = walk(tree, l, r, x, l_child[tree][u]);
    if (l_resp != r + 1) return l_resp;
    return walk(tree, l, r, x, r_child[tree][u]);
}

void merge_update(int tree1, int tree2, int u = 1) {
    if (l_child[tree1][u] == 0) {
        add_update(tree2, lo[tree1][u], hi[tree1][u], segtree[tree1][u].ans);
        return;
    }

    expand(tree1, u);
    propogate(tree1, u);
    merge_update(tree1, tree2, l_child[tree1][u]);
    merge_update(tree1, tree2, r_child[tree1][u]);
}
void merge(int u, int v) {
    if (n_nodes[u] < n_nodes[v]) {
        swap(n_nodes[u], n_nodes[v]);
        segtree[u].swap(segtree[v]);
        lo[u].swap(lo[v]);
        hi[u].swap(hi[v]);
        l_child[u].swap(l_child[v]);
        r_child[u].swap(r_child[v]);
    }

    merge_update(v, u);
}

void dfs(int u) {
    for (int v : children[u]) {
        dfs(v);
        merge(u, v);
    }

    // cout << u << ": " << query(u, MAX_K) << endl;
    if (val[u] == 0) return;
    lint take = query(u, t[u]) + val[u];
    assert(take != 0);
    // cout << u << ": " << take << " " << walk(u, t[u], MAX_K, take) - 1 << endl;
    set_update(u, t[u], walk(u, t[u], MAX_K, take) - 1, take);
    // cout << u << ": " << query(u, MAX_K) << endl;
}

int main() {
    // freopen("tree.in", "r", stdin);
    // freopen("tree.out", "w", stdout);

    cin >> n >> m >> k;
    for (int i = 2; i <= n; i++) {
        int p; cin >> p;
        children[p].push_back(i);
    }
    for (int i = 1; i <= m; i++) {
        int u; cin >> u;
        cin >> t[u] >> val[u]; 
    }

    init();
    dfs(1);

    cout << query(1, MAX_K) << '\n';
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 15964 KB Output is correct
2 Correct 4 ms 15964 KB Output is correct
3 Correct 4 ms 15964 KB Output is correct
4 Correct 4 ms 15964 KB Output is correct
5 Correct 4 ms 16216 KB Output is correct
6 Correct 4 ms 15964 KB Output is correct
7 Correct 4 ms 15964 KB Output is correct
8 Correct 4 ms 15964 KB Output is correct
9 Correct 4 ms 15964 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 524 ms 174072 KB Output is correct
2 Correct 233 ms 96660 KB Output is correct
3 Correct 1542 ms 457112 KB Output is correct
4 Correct 711 ms 262964 KB Output is correct
5 Correct 753 ms 264948 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 16220 KB Output is correct
2 Correct 5 ms 16220 KB Output is correct
3 Correct 5 ms 16216 KB Output is correct
4 Correct 191 ms 54504 KB Output is correct
5 Correct 169 ms 54204 KB Output is correct
6 Correct 246 ms 55408 KB Output is correct

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 467 ms 153684 KB Output is correct
2 Incorrect 454 ms 153168 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 15964 KB Output is correct
2 Correct 4 ms 15964 KB Output is correct
3 Correct 4 ms 15964 KB Output is correct
4 Correct 4 ms 15964 KB Output is correct
5 Correct 4 ms 16216 KB Output is correct
6 Correct 4 ms 15964 KB Output is correct
7 Correct 4 ms 15964 KB Output is correct
8 Correct 4 ms 15964 KB Output is correct
9 Correct 4 ms 15964 KB Output is correct
10 Incorrect 530 ms 157876 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 24208 KB Output is correct
2 Correct 96 ms 40984 KB Output is correct
3 Correct 95 ms 41028 KB Output is correct
4 Correct 100 ms 42112 KB Output is correct
5 Correct 63 ms 38608 KB Output is correct
6 Incorrect 98 ms 40404 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 15964 KB Output is correct
2 Correct 4 ms 15964 KB Output is correct
3 Correct 4 ms 15964 KB Output is correct
4 Correct 4 ms 15964 KB Output is correct
5 Correct 4 ms 16216 KB Output is correct
6 Correct 4 ms 15964 KB Output is correct
7 Correct 4 ms 15964 KB Output is correct
8 Correct 4 ms 15964 KB Output is correct
9 Correct 4 ms 15964 KB Output is correct
10 Correct 5 ms 16220 KB Output is correct
11 Correct 5 ms 16220 KB Output is correct
12 Correct 5 ms 16216 KB Output is correct
13 Correct 191 ms 54504 KB Output is correct
14 Correct 169 ms 54204 KB Output is correct
15 Correct 246 ms 55408 KB Output is correct
16 Incorrect 530 ms 157876 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 15964 KB Output is correct
2 Correct 4 ms 15964 KB Output is correct
3 Correct 4 ms 15964 KB Output is correct
4 Correct 4 ms 15964 KB Output is correct
5 Correct 4 ms 16216 KB Output is correct
6 Correct 4 ms 15964 KB Output is correct
7 Correct 4 ms 15964 KB Output is correct
8 Correct 4 ms 15964 KB Output is correct
9 Correct 4 ms 15964 KB Output is correct
10 Correct 524 ms 174072 KB Output is correct
11 Correct 233 ms 96660 KB Output is correct
12 Correct 1542 ms 457112 KB Output is correct
13 Correct 711 ms 262964 KB Output is correct
14 Correct 753 ms 264948 KB Output is correct
15 Correct 5 ms 16220 KB Output is correct
16 Correct 5 ms 16220 KB Output is correct
17 Correct 5 ms 16216 KB Output is correct
18 Correct 191 ms 54504 KB Output is correct
19 Correct 169 ms 54204 KB Output is correct
20 Correct 246 ms 55408 KB Output is correct
21 Correct 467 ms 153684 KB Output is correct
22 Incorrect 454 ms 153168 KB Output isn't correct
23 Halted 0 ms 0 KB -