oj.uz

Submission #723624

# Submission time Handle Problem Language Result Execution time Memory
723624 2023-04-14T06:31:56 Z MDSPro Magic Tree (CEOI19_magictree) C++17
34 / 100
 1900 ms 49224 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);
    }

    for(int i = 0,v; i < m; ++i) {
        cin >> v; cin >> rday[v] >> cost[v];
    }

    for(int i = 0; i <= n; ++i){
        for(int j = 0; j <= k+1; ++j){
            dp[i][j] = -1;
        }
    }

    cout << get(1,k+1);
}

Subtask #1
6.0 / 6.0

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

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 1900 ms 49224 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

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 156 ms 24620 KB Output is correct
2 Correct 147 ms 24520 KB Output is correct
3 Correct 141 ms 28624 KB Output is correct
4 Correct 121 ms 23492 KB Output is correct
5 Correct 115 ms 33836 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 284 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 142 ms 24508 KB Output is correct
11 Correct 143 ms 24572 KB Output is correct
12 Correct 182 ms 28624 KB Output is correct
13 Correct 113 ms 23424 KB Output is correct
14 Correct 133 ms 33868 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 261 ms 10316 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 212 KB Output is correct
2 Correct 0 ms 284 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 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 0 ms 212 KB Output is correct
2 Correct 0 ms 284 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Runtime error 1900 ms 49224 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -