Submission #957826

#	Time	Username	Problem	Language	Result	Execution time	Memory
957826		Ghetto	Magic Tree (CEOI19_magictree)	C++17	100 / 100	1668 ms	454788 KiB

magictree

#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;
        segtree[tree][l_child[tree][u]].lazy_add = 0;
        segtree[tree][r_child[tree][u]].lazy_add = 0;
    }
    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) {
        // cout << tree1 << " " << tree2 << " " << segtree[tree1][u].ans << endl;
        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 invis_traverse(int tree, int u = 1) {
    cout << tree << " " << lo[tree][u] << " " << hi[tree][u] << ": " << segtree[tree][u].ans << " " << segtree[tree][u].lazy_set << " " << segtree[tree][u].lazy_add << endl;
    
    if (l_child[tree][u] == 0) return;

    invis_traverse(tree, l_child[tree][u]);
    invis_traverse(tree, r_child[tree][u]);
}

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

    if (val[u] == 0) return;
    lint take = query(u, t[u]) + val[u];
    set_update(u, t[u], walk(u, t[u], MAX_K, take) - 1, take);
}

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 / 6
• Subtask 2: 3 / 3
• Subtask 3: 11 / 11
• Subtask 4: 12 / 12
• Subtask 5: 16 / 16
• Subtask 6: 13 / 13
• Subtask 7: 22 / 22
• Subtask 8: 17 / 17