Submission #1239897

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239897		Double_Slash	Magic Tree (CEOI19_magictree)	C++20	100 / 100	136 ms	31636 KiB

magictree

#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;

int n, m, k, d[100001], w[100001], sz;
struct Node {
    ll sum;
    int lc, rc;
} mem[1 << 21];
vector<int> adj[100001];

void upd(int &n, int i, int v, int l, int r) {
    if (not n) n = ++sz;
    mem[n].sum += v;
    if (l == r) return;
    int m = (l + r) >> 1;
    if (i <= m) upd(mem[n].lc, i, v, l, m);
    else upd(mem[n].rc, i, v, m + 1, r);
}

void erase(int &n, int i, int &v, int l, int r) {
    if (l > i or not v) return;
    if (r <= i and mem[n].sum <= v) {
        v -= mem[n].sum;
        n = 0;
    }
    if (not n) return;
    if (l == r) {
        mem[n].sum -= v;
        v = 0;
        return;
    }
    int m = (l + r) >> 1;
    erase(mem[n].rc, i, v, m + 1, r);
    erase(mem[n].lc, i, v, l, m);
    mem[n].sum = mem[mem[n].lc].sum + mem[mem[n].rc].sum;
}

int merge(int a, int b) {
    if (not a or not b) return max(a, b);
    mem[a].sum += mem[b].sum;
    mem[a].lc = merge(mem[a].lc, mem[b].lc);
    mem[a].rc = merge(mem[a].rc, mem[b].rc);
    return a;
}

int dfs(int i) {
    int root = 0;
    for (int j: adj[i]) root = merge(root, dfs(j));
    upd(root, -d[i], w[i], -k, -1);
    erase(root, -d[i] - 1, w[i], -k, -1);
    return root;
}

int main() {
    cin >> n >> m >> k;
    for (int i = 2; i <= n; ++i) {
        int p;
        cin >> p;
        adj[p].emplace_back(i);
    }
    while (m--) {
        int v;
        cin >> v >> d[v] >> w[v];
    }
    cout << mem[dfs(1)].sum;
}

• 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