oj.uz

Submission #957805

# Submission time Handle Problem Language Result Execution time Memory
957805 2024-04-04T10:53:56 Z Ghetto Magic Tree (CEOI19_magictree) C++17
32 / 100
 1869 ms 537672 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 << " " << segtree[tree][u].lazy_set << " " << segtree[tree][u].lazy_add << 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;

    query(u, MAX_K);

    if (val[u] == 0) return;
    lint take = query(u, t[u]) + val[u];
    // 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;

    // 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 15960 KB Output is correct
2 Correct 5 ms 15964 KB Output is correct
3 Correct 4 ms 16132 KB Output is correct
4 Correct 4 ms 15960 KB Output is correct
5 Correct 4 ms 15964 KB Output is correct
6 Correct 4 ms 15964 KB Output is correct
7 Correct 4 ms 16016 KB Output is correct
8 Correct 4 ms 15964 KB Output is correct
9 Correct 3 ms 15964 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 846 ms 272356 KB Output is correct
2 Correct 322 ms 115744 KB Output is correct
3 Correct 1869 ms 537672 KB Output is correct
4 Correct 1168 ms 367836 KB Output is correct
5 Correct 1083 ms 348120 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 16420 KB Output is correct
3 Correct 5 ms 16220 KB Output is correct
4 Correct 206 ms 54332 KB Output is correct
5 Correct 180 ms 54268 KB Output is correct
6 Correct 264 ms 54792 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 721 ms 300660 KB Output is correct
2 Correct 756 ms 299416 KB Output is correct
3 Correct 427 ms 144620 KB Output is correct
4 Correct 1077 ms 535788 KB Output is correct
5 Correct 171 ms 44644 KB Output is correct

Subtask #5
0 / 16.0

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

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 48012 KB Output is correct
2 Correct 442 ms 163216 KB Output is correct
3 Correct 411 ms 162916 KB Output is correct
4 Correct 424 ms 163804 KB Output is correct
5 Correct 568 ms 276684 KB Output is correct
6 Incorrect 435 ms 187376 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 15960 KB Output is correct
2 Correct 5 ms 15964 KB Output is correct
3 Correct 4 ms 16132 KB Output is correct
4 Correct 4 ms 15960 KB Output is correct
5 Correct 4 ms 15964 KB Output is correct
6 Correct 4 ms 15964 KB Output is correct
7 Correct 4 ms 16016 KB Output is correct
8 Correct 4 ms 15964 KB Output is correct
9 Correct 3 ms 15964 KB Output is correct
10 Correct 5 ms 16220 KB Output is correct
11 Correct 5 ms 16420 KB Output is correct
12 Correct 5 ms 16220 KB Output is correct
13 Correct 206 ms 54332 KB Output is correct
14 Correct 180 ms 54268 KB Output is correct
15 Correct 264 ms 54792 KB Output is correct
16 Incorrect 762 ms 270416 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 15960 KB Output is correct
2 Correct 5 ms 15964 KB Output is correct
3 Correct 4 ms 16132 KB Output is correct
4 Correct 4 ms 15960 KB Output is correct
5 Correct 4 ms 15964 KB Output is correct
6 Correct 4 ms 15964 KB Output is correct
7 Correct 4 ms 16016 KB Output is correct
8 Correct 4 ms 15964 KB Output is correct
9 Correct 3 ms 15964 KB Output is correct
10 Correct 846 ms 272356 KB Output is correct
11 Correct 322 ms 115744 KB Output is correct
12 Correct 1869 ms 537672 KB Output is correct
13 Correct 1168 ms 367836 KB Output is correct
14 Correct 1083 ms 348120 KB Output is correct
15 Correct 5 ms 16220 KB Output is correct
16 Correct 5 ms 16420 KB Output is correct
17 Correct 5 ms 16220 KB Output is correct
18 Correct 206 ms 54332 KB Output is correct
19 Correct 180 ms 54268 KB Output is correct
20 Correct 264 ms 54792 KB Output is correct
21 Correct 721 ms 300660 KB Output is correct
22 Correct 756 ms 299416 KB Output is correct
23 Correct 427 ms 144620 KB Output is correct
24 Correct 1077 ms 535788 KB Output is correct
25 Correct 171 ms 44644 KB Output is correct
26 Incorrect 762 ms 270416 KB Output isn't correct
27 Halted 0 ms 0 KB -