Submission #1082321

#	Time	Username	Problem	Language	Result	Execution time	Memory
1082321		dwuy	Magic Tree (CEOI19_magictree)	C++14	100 / 100	85 ms	43088 KiB

magictree

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int MX = 200005;
int n, m, k;
int d[MX];
int w[MX];
map<int, int> f[MX];
vector<int> G[MX];

void dfs(int u){
    for(int v: G[u]){
        dfs(v);
        if(f[v].size() > f[u].size()) swap(f[u], f[v]);
        for(pair<int, int> tmp: f[v]){
            f[u][tmp.first] += tmp.second;
        }
        f[v].clear();
    }
    if(d[u]){
        f[u][d[u]] += w[u];
        while(1){
            auto itr = f[u].upper_bound(d[u]);
            if(itr == f[u].end()) break;
            if(itr->second <= w[u]){
                w[u] -= itr->second;
                f[u].erase(itr);
            }
            else{
                itr->second -= w[u];
                break;
            }
        }
    }
}

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m >> k;
    for(int i=2; i<=n; i++){
        int p; cin >> p;
        G[p].push_back(i);
    }
    for(int i=1; i<=m; i++){
        int u; cin >> u;
        cin >> d[u] >> w[u];
    }
    dfs(1);
    int ans = 0;
    for(pair<int, int> tmp: f[1]) ans += tmp.second;
    cout << ans;

    return 0;
}

• 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