제출 #1320361

#제출 시각아이디문제언어결과실행 시간메모리
1320361vaishakhvMagic Tree (CEOI19_magictree)C++20
0 / 100
27 ms4260 KiB
// Source: https://usaco.guide/general/io

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define eb emplace_back

#define m1(x) template<class T, class... U> void x(T&& a, U&&... b)
#define m2(x) (ll[]){(x forward<U>(b),0)...}

m1(pr){cout << forward<T>(a);  m2(cout << " " <<); cout << "\n";}
m1(re){cin >> forward<T>(a); m2(cin >>);}

ll n, m, k;
vector<vector<ll>> adj;
map<ll, pair<ll, ll>> fruit;
vector<vector<ll>> dp;

/*
void dfs(ll u) {
    ll fruit_day = k+1, fruit_juice = 0;
    if (fruit.count(u)) {
        fruit_day = fruit[u].first;
        fruit_juice = fruit[u].second;
    }
    
    for (ll t = 0; t <= k; t++) {
        if (t >= fruit_day) dp[u][t] = fruit_juice;
    }
    
    for (ll c : adj[u]) {
        dfs(c);
        
        vector<ll> tmp(k+1, 0);
        for (ll t1 = 0; t1 <= k; t1++) {
            for (ll t2 = 0; t2 <= k; t2++) {
                ll t_max = max(t1, t2);
                tmp[t_max] = max(tmp[t_max], dp[u][t1] + dp[c][t2]);
            }
        }
        dp[u] = tmp;
    }
    
    for (ll t = 1; t <= k; t++) {
        dp[u][t] = max(dp[u][t], dp[u][t-1]);
    }
}
*/

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    re(n, m, k);
    
    vector<ll> parent(n+1);
    for (ll i = 2; i <= n; i++) {
        re(parent[i]);
    }

    vector<tuple<ll, ll, ll>> fruits; 
    for (ll i{}; i < m; i++) {
        ll v, d, w; 
        re(v, d, w);
        fruits.eb(v, d, w);
    }
    
    sort(fruits.begin(), fruits.end(), greater<tuple<ll,ll,ll>>());
    
    ll ans = 0;
    ll cutb4 = k + 1; 
    
    for (auto tup:fruits) {
        ll v, d, w;
        tie(v, d, w) = tup;
        if (d < cutb4) {
            ans += w; 
            cutb4 = d; 
        }
    }
    
    pr(ans);
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...