oj.uz

Submission #880406

# Submission time Handle Problem Language Result Execution time Memory
880406 2023-11-29T10:58:57 Z Trisanu_Das Magic Tree (CEOI19_magictree) C++17
37 / 100
 117 ms 36076 KB 
#include "bits/stdc++.h"
 
using namespace std;
const int MAXN = 1e5+10;
const int INF = 1e9;
 
int n,m,k;
vector<int> cost;
vector<int> rday;
vector<vector<int>> g;
long long dp[MAXN][25];
 
long long get(int v, int md){
    if(dp[v][md] != -1) return dp[v][md];
    if(md == 0) return dp[v][md] = 0;
 
    dp[v][md] = (rday[v] == md ? cost[v] : 0);
    for(int z: g[v]) dp[v][md] += get(z,md);
 
    return dp[v][md] = max(dp[v][md],get(v,md-1));
}
 
int main(){
    cin >> n >> m >> k;
    g.resize(n+1);
    cost.reserve(n+1);
    rday.assign(n+1,INF);
    for(int i = 2,x; i <= n; ++i){
        cin >> x;
        g[x].emplace_back(i);
    }
 
    int cnt = 0;
    long long sum = 0;
    for(int i = 0,v; i < m; ++i) {
        cin >> v; cin >> rday[v] >> cost[v];
        if(g[v].size() == 0) {
            cnt++;
            sum += cost[v];
        }
    }
 
    if(cnt == m){
        cout << sum;
        return 0;
    }
 
    for(int i = 0; i <= n; ++i){
        for(int j = 0; j <= k+1; ++j){
            dp[i][j] = -1;
        }
    }
 
    cout << get(1,k+1);
    return 0;
}

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 0 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
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 5968 KB Output is correct
2 Correct 38 ms 6700 KB Output is correct
3 Correct 80 ms 6488 KB Output is correct
4 Correct 69 ms 5996 KB Output is correct
5 Correct 105 ms 6780 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Incorrect 1 ms 2652 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 26808 KB Output is correct
2 Correct 88 ms 26728 KB Output is correct
3 Correct 92 ms 30800 KB Output is correct
4 Correct 75 ms 25292 KB Output is correct
5 Correct 86 ms 36076 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 0 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 117 ms 26196 KB Output is correct
11 Correct 101 ms 26164 KB Output is correct
12 Correct 108 ms 30292 KB Output is correct
13 Correct 76 ms 24568 KB Output is correct
14 Correct 89 ms 35840 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 114 ms 12372 KB Output isn't correct
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 0 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 1 ms 2652 KB Output is correct
11 Incorrect 1 ms 2652 KB Output isn't correct
12 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 0 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 41 ms 5968 KB Output is correct
11 Correct 38 ms 6700 KB Output is correct
12 Correct 80 ms 6488 KB Output is correct
13 Correct 69 ms 5996 KB Output is correct
14 Correct 105 ms 6780 KB Output is correct
15 Correct 1 ms 2652 KB Output is correct
16 Incorrect 1 ms 2652 KB Output isn't correct
17 Halted 0 ms 0 KB -