Submission #1094514

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1094514	2024-09-29T18:02:46 Z	vladilius	Magic Tree (CEOI19_magictree)	C++17	34 / 100	418 ms	1048576 KB

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.0 / 6.0

#	Verdict	Memory	Grader output
1	Correct	348 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Correct	348 KB	Output is correct
4	Correct	348 KB	Output is correct
5	Correct	604 KB	Output is correct
6	Correct	456 KB	Output is correct
7	Correct	344 KB	Output is correct
8	Correct	348 KB	Output is correct
9	Correct	348 KB	Output is correct

Subtask #2
0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	403 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	8280 KB	Output is correct
2	Correct	5 ms	8280 KB	Output is correct
3	Correct	5 ms	8284 KB	Output is correct
4	Runtime error	410 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	12636 KB	Output is correct
2	Correct	39 ms	13016 KB	Output is correct
3	Correct	36 ms	16976 KB	Output is correct
4	Correct	30 ms	11040 KB	Output is correct
5	Correct	34 ms	22108 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	604 KB	Output is correct
6	Correct	0 ms	456 KB	Output is correct
7	Correct	0 ms	344 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	54 ms	26196 KB	Output is correct
11	Correct	44 ms	18208 KB	Output is correct
12	Correct	55 ms	30244 KB	Output is correct
13	Correct	37 ms	24536 KB	Output is correct
14	Correct	43 ms	35604 KB	Output is correct

Subtask #6
0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	418 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	604 KB	Output is correct
6	Correct	0 ms	456 KB	Output is correct
7	Correct	0 ms	344 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	8280 KB	Output is correct
11	Correct	5 ms	8280 KB	Output is correct
12	Correct	5 ms	8284 KB	Output is correct
13	Runtime error	410 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	604 KB	Output is correct
6	Correct	0 ms	456 KB	Output is correct
7	Correct	0 ms	344 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	403 ms	1048576 KB	Execution killed with signal 9
11	Halted	0 ms	0 KB	-

Submission #1094514

Compilation message