Submission #945785

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
945785	2024-03-14T07:45:28 Z	vjudge1	Magic Tree (CEOI19_magictree)	C++17	34 / 100	487 ms	1048576 KB

magictree

#include <bits/stdc++.h>

using namespace std;

#define all(x) x.begin(), x.end()
#define ar array
#define pb push_back
#define ln '\n'
#define int long long

using i64 = long long;

template <class F, class _S>
bool chmin(F &u, const _S &v){
    bool flag = false;
    if ( u > v ){
        u = v; flag |= true;
    }
    return flag;
}

template <class F, class _S>
bool chmax(F &u, const _S &v){
    bool flag = false;
    if ( u < v ){
        u = v; flag |= true;
    }
    return flag;
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, k; cin >> n >> m >> k;
    vector <vector<int>> G(n);
    for ( int i = 1; i < n; i++ ){
        int p; cin >> p;
        --p;
        G[p].pb(i);
    }
    vector <int> w(n), d(n);
    for ( int i = 0; i < m; i++ ){
        int d_, v, w_; cin >> v >> d_ >> w_;
        --v;
        w[v] = w_;
        d[v] = d_;
    }
    vector <vector<int>> dp(n, vector <int> (k + 1));
    auto dfs = [&](auto dfs, int u) -> void{
        for ( auto &v: G[u] ){
            dfs(dfs, v);
        }
        for ( int j = 1; j <= k; j++ ){
            int opt = 0;
            for ( auto &v: G[u] ){
                opt += dp[v][j];
            }
            chmax(dp[u][j], dp[u][j - 1]);
            if ( j <= d[u] ){
                chmax(dp[u][d[u]], opt + w[u]);
            }
            chmax(dp[u][j], opt);
        }
    };
    dfs(dfs, 0);
    cout << dp[0][k];

    cout << '\n';
}

Subtask #1
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct

Subtask #2
0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	487 ms	1048576 KB	Execution killed with signal 9
2	Halted	0 ms	0 KB	-

Subtask #3
0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	8284 KB	Output is correct
2	Correct	6 ms	8464 KB	Output is correct
3	Correct	6 ms	8284 KB	Output is correct
4	Runtime error	382 ms	1048576 KB	Execution killed with signal 9
5	Halted	0 ms	0 KB	-

Subtask #4
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	44 ms	11604 KB	Output is correct
2	Correct	39 ms	11604 KB	Output is correct
3	Correct	49 ms	14932 KB	Output is correct
4	Correct	27 ms	10700 KB	Output is correct
5	Correct	37 ms	19536 KB	Output is correct

Subtask #5
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	75 ms	25804 KB	Output is correct
11	Correct	61 ms	17756 KB	Output is correct
12	Correct	82 ms	29008 KB	Output is correct
13	Correct	51 ms	24532 KB	Output is correct
14	Correct	49 ms	33628 KB	Output is correct

Subtask #6
0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	355 ms	1048576 KB	Execution killed with signal 9
2	Halted	0 ms	0 KB	-

Subtask #7
0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	6 ms	8284 KB	Output is correct
11	Correct	6 ms	8464 KB	Output is correct
12	Correct	6 ms	8284 KB	Output is correct
13	Runtime error	382 ms	1048576 KB	Execution killed with signal 9
14	Halted	0 ms	0 KB	-

Subtask #8
0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Runtime error	487 ms	1048576 KB	Execution killed with signal 9
11	Halted	0 ms	0 KB	-

Submission #945785

Compilation message