Submission #1180387

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180387		Ludissey	Magic Tree (CEOI19_magictree)	C++20	0 / 100	2096 ms	16372 KiB

magictree

#include <bits/stdc++.h>
using namespace std;
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define int long long

vector<vector<int>> child;
vector<int> w,d;


map<int,int> dp(int x){
    vector<map<int,int>> v;
    for (auto u : child[x])
    {
        v.push_back(dp(u));
    }
    sort(all(v), [](map<int,int> a, map<int,int> b){return sz(a)>sz(b);});
    for (int i = 1; i < sz(v); i++)
    {
        if(sz(v[i])==0) continue; 
        for (auto u : v[i])
        {
            v[0][u.first]+=u.second;
        }
    }
    if(sz(v)>0){
        if(w[x]==0) return v[0];
        auto it=v[0].upper_bound(d[x]);
        if(it!=v[0].end()) {
            v[0][(*it).first]-=w[x];
        }
        v[0][d[x]]+=w[x];
    }else{
        v.resize(1);
        if(w[x]==0) return v[0];
        v[0][d[x]]=w[x];
    }
    return v[0];
}

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int n,m,k; cin >> n >> m >> k;
    child.resize(n);
    w.resize(n,0);
    d.resize(n,0);
    for (int i = 1; i < n; i++)
    {
        int p; cin >> p;
        child[p-1].push_back(i);
    }
    for (int i = 0; i < n; i++) {
        int v; cin >> v;
        cin >> d[v-1] >> w[v-1];
    }
    map<int,int> mp=dp(0);
    int mx=0;
    for (auto u : mp) mx+=u.second;
    cout << mx << "\n";
    return 0;
}

• Subtask 1: 0 / 6
• Subtask 2: 0 / 3
• Subtask 3: 0 / 11
• Subtask 4: 0 / 12
• Subtask 5: 0 / 16
• Subtask 6: 0 / 13
• Subtask 7: 0 / 22
• Subtask 8: 0 / 17