Submission #972822

#	Time	Username	Problem	Language	Result	Execution time	Memory
972822		phoenix	Magic Tree (CEOI19_magictree)	C++17	34 / 100	555 ms	1048576 KiB

magictree

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int n, m, k;

const int N = 100100;

int w[N];
int d[N];
int p[N];

int main() {
    ios::sync_with_stdio(0),
    cin.tie(0);
    cin >> n >> m >> k;
    for (int i = 2; i <= n; i++) 
        cin >> p[i];
    for (int i = 0; i < m; i++) {
        int u;
        cin >> u;
        cin >> d[u] >> w[u];
    }
    vector<vector<ll>> dp(n + 1, vector<ll>(k + 1, 0));
    for (int i = n; i >= 1; i--) {
        ll val = dp[i][d[i]] + w[i];
        for (int j = d[i]; j <= k; j++) 
            dp[i][j] = max(dp[i][j], val);
        for (int j = 1; j <= k; j++) 
            dp[p[i]][j] += dp[i][j];
    }
    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