Submission #1361286

#TimeUsernameProblemLanguageResultExecution timeMemory
1361286AliMark71Magic Tree (CEOI19_magictree)C++20
100 / 100
76 ms26152 KiB
//
//  main.cpp
//  IntensiveCamp 1 2026
//
//  Created by Ali AlSalman on 27/04/2026.
//

#include <bits/stdc++.h>

#pragma GCC target("popcnt")

//#define INTERACTIVE
//#define TESTCASES
//#define SPOJ_BULLSCHEI__SZ__E__KIJETESANPAKALU__

#ifndef INTERACTIVE
#define endl '\n'
#endif

template<typename T>
using vec = std::vector<T>;
using namespace std;

struct G {
    int size;
    vec<vec<int>> adj;;
    G(int n) : size(n), adj(n) {}
    
    void undirectedAdd(int i, int j) {
        adj[i].push_back(j);
        adj[j].push_back(i);
    }
    
};
    
typedef map<int, long long> darr;
darr* merge(darr* a, darr* b) {
    if (a->size() > b->size()) swap(a, b);
    for (auto [k, v] : *a)
        (*b)[k] += v;
    delete a;
    return b;
}

vec<darr::iterator> to_remove;

void dfs(int u, int p, G& g, vec<darr*>& dp, vec<array<int, 2>>& f) {
    dp[u] = new darr;
    for (auto c : g.adj[u]) if (c != p) {
        dfs(c, u, g, dp, f);
        dp[u] = merge(dp[u], dp[c]);
    }
    
    auto [d, w] = f[u];
    (*dp[u])[d] += w;
    
    for (auto it = next(dp[u]->find(d)); w && it != dp[u]->end(); ++it) {
        if (it->second > w) { it->second -= w; break; }
        w -= it->second;
        to_remove.push_back(it);
    }
    while (!to_remove.empty()) {
        dp[u]->erase(to_remove.back());
        to_remove.pop_back();
    }
}

void solve() {
    int n, m, k;
    cin>>n>>m>>k;
    
    G g(n);
    for (int i = 1; i < n; i++) {
        int j;
        cin>>j; j--;
        g.undirectedAdd(i, j);
    }
    
    vec<array<int, 2>> f(n);
    while (m--) {
        int a, b, c;
        cin>>a>>b>>c; a--;
        f[a] = {b, c};
    }
    
    vec<darr*> dp(n);
    dfs(0, -1, g, dp, f);
    
    long long ans = 0;
    for (auto [t, v] : *dp[0]) {
        if (k < t) break;
        ans += v;
    }
    
    cout<<ans<<endl;
}

int main() {
#ifndef INTERACTIVE
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#endif
    
    int t = 1;
#ifdef TESTCASES
    cin>>t;
#endif
    
    for (int i = t; i--;) {
#if defined(TESTCASES) && defined(SPOJ_BULLSCHEI__SZ__E__KIJETESANPAKALU__)
        cout<<"Case "<<t-i<<":\n";
#elif defined(SPOJ_BULLSCHEI__SZ__E__KIJETESANPAKALU__)
#warning SPOJ_BULLSCHEI�E__KIJETESANPAKALU__ without TESTCASES doesn't ducking make sense!
#endif
        solve();
    }
    return 0;
}

Compilation message (stderr)

magictree.cpp:112:69: warning: missing terminating ' character
  112 | #warning SPOJ_BULLSCHEI�E__KIJETESANPAKALU__ without TESTCASES doesn't ducking make sense!
      |                                                                     ^
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...