Submission #447318

#	Time	Username	Problem	Language	Result	Execution time	Memory
447318		SirCovidThe19th	Magic Tree (CEOI19_magictree)	C++14	100 / 100	218 ms	31148 KiB

magictree

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

#define ll long long
#define mil map<int, ll>
#define f first
#define s second

const int mx = 1e5+5;

int n, m, k; pair<int, int> F[mx]; vector<int> adj[mx]; ll ans = 0;

void dfs(mil &mp, int i){
    for (int x : adj[i]){
        mil tmp; dfs(tmp, x);
        if (tmp.size() > mp.size()) swap(mp, tmp);
        for (auto elem : tmp) mp[elem.f] += elem.s;
    }if (F[i].f){
        mp[F[i].f] += F[i].s;
        auto it = mp.upper_bound(F[i].f); 
        for (ll diff = 0; it != mp.end();){
            int pos = it->f; diff += it->s; it = mp.erase(it);
            if (diff > F[i].s){ mp[pos] = diff-F[i].s; break; }
        }
    }
}

int main(){
    cin >> n >> m >> k;
    for (int i = 1; i < n; i++){ int a; cin >> a; adj[a-1].push_back(i); }
    for (int i = 0; i < m; i++){ int v, d, w; cin >> v >> d >> w; F[v-1] = {d, w}; }
    mil mp; dfs(mp, 0); for (auto x : mp){ ans += x.s; } cout<<ans<<endl;
}

• 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