제출 #1320357

#제출 시각아이디문제언어결과실행 시간메모리
1320357vaishakhvMagic Tree (CEOI19_magictree)C++20
0 / 100
558 ms1114112 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) {
    if (fruit.count(u)) {
        ll day = fruit[u].first;
        ll juice = fruit[u].second;
        for (ll t = day; t <= k; t++) {
            dp[u][t] = juice;
        }
    }
    
    for (ll c : adj[u]) {
        dfs(c);
        
        vector<ll> tmp(k+1, 0);
        for (ll t{}; t <= k; t++) {
            for (ll t2 = 0; t2 <= t; t2++) {  // t2 <= t (child cut by day t2)
                tmp[t] = max(tmp[t], dp[u][t] + dp[c][t2]);
            }
        }
        dp[u] = tmp;
    }
}

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

    re(n, m, k);
    
    adj.resize(n+1);
    dp.assign(n+1, vector<ll>(k+1, 0));
    
    for (ll i = 2; i <= n; i++) {
        ll p; re(p);
        adj[p].eb(i);
    }

    for (ll i{}; i < m; i++) {
        ll v, d, w; 
        re(v, d, w);
        fruit[v] = {d, w};
    }

    dfs(1);
    
    ll ans = 0;
    for (ll t{}; t <= k; t++) {
        ans = max(ans, dp[1][t]);
    }
    
    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...