oj.uz

Submission #723628

# Submission time Handle Problem Language Result Execution time Memory
723628 2023-04-14T06:34:11 Z MDSPro Magic Tree (CEOI19_magictree) C++17
37 / 100
 255 ms 33952 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 1 ms 240 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 4780 KB Output is correct
2 Correct 78 ms 6520 KB Output is correct
3 Correct 124 ms 6476 KB Output is correct
4 Correct 117 ms 5992 KB Output is correct
5 Correct 124 ms 6568 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 596 KB Output is correct
2 Incorrect 2 ms 596 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 164 ms 24544 KB Output is correct
2 Correct 173 ms 24516 KB Output is correct
3 Correct 167 ms 28596 KB Output is correct
4 Correct 120 ms 23520 KB Output is correct
5 Correct 148 ms 33952 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 240 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 159 ms 24508 KB Output is correct
11 Correct 163 ms 24636 KB Output is correct
12 Correct 149 ms 28596 KB Output is correct
13 Correct 125 ms 23400 KB Output is correct
14 Correct 143 ms 33948 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 255 ms 10220 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 240 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 2 ms 596 KB Output is correct
11 Incorrect 2 ms 596 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 240 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 59 ms 4780 KB Output is correct
11 Correct 78 ms 6520 KB Output is correct
12 Correct 124 ms 6476 KB Output is correct
13 Correct 117 ms 5992 KB Output is correct
14 Correct 124 ms 6568 KB Output is correct
15 Correct 2 ms 596 KB Output is correct
16 Incorrect 2 ms 596 KB Output isn't correct
17 Halted 0 ms 0 KB -