Submission #722544

#	Time	Username	Problem	Language	Result	Execution time	Memory
722544		bitaro1337	Magic Tree (CEOI19_magictree)	C++14	100 / 100	222 ms	37772 KiB

magictree

//BITARO BITARO BITARO
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;
vector<int> adj[N];
map<int64_t, int64_t> mp[N];
int64_t d[N], w[N], ans;
void dfs(int u) {
    for(int v: adj[u]) {
        dfs(v);
        if(mp[v].size() > mp[u].size()) swap(mp[u], mp[v]);
        for(auto x: mp[v]) mp[u][x.first] += x.second;
    }
    if(!d[u]) return;
    mp[u][d[u]] += w[u];
    int64_t val = w[u];
    while(val > 0) {
        auto it = mp[u].upper_bound(d[u]);
        if(it == mp[u].end()) break;
        int64_t vv = it->second;
        if(val >= vv) {
            mp[u].erase(it);
        } else {
            it->second -= val;
        }
        val -= vv;
    }
}
int main() {
    int n, m, k; cin >> n >> m >> k;
    for(int i = 2; i <= n; ++i) {
        int x; cin >> x;
        adj[x].push_back(i);
    }
    for(int i = 0; i < m; ++i) {
        int a, b, c; cin >> a >> b >> c;
        d[a] = b;
        w[a] = c;
    }
    dfs(1);
    for(auto x: mp[1]) ans += x.second;
    cout << ans << "\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