Submission #1094514

#	Time	Username	Problem	Language	Result	Execution time	Memory
1094514		vladilius	Magic Tree (CEOI19_magictree)	C++17	34 / 100	418 ms	1048576 KiB

magictree

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n, m, k; cin>>n>>m>>k;
    vector<int> g[n + 1];
    for (int i = 2; i <= n; i++){
        int p; cin>>p;
        g[p].pb(i);
    }
    vector<int> d(n + 1), w(n + 1);
    for (int i = 1; i <= m; i++){
        int u, x, y; cin>>u>>x>>y;
        d[u] = x; w[u] = y;
    }
    
    vector<vector<ll>> dp(n + 1, vector<ll>(k + 1));
    
    function<void(int)> solve = [&](int v){
        for (int i: g[v]){
            solve(i);
        }
        for (int i = 1; i <= k; i++){
            for (int j: g[v]){
                dp[v][i] += dp[j][i];
            }
        }
        if (w[v] != -1){
            ll S = w[v];
            for (int j: g[v]){
                S += dp[j][d[v]];
            }
            for (int i = d[v]; i <= k; i++){
                dp[v][i] = max(dp[v][i], S);
            }
        }
    };
    solve(1);
    cout<<dp[1][k]<<"\n";
}

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