oj.uz

Submission #723591

# Submission time Handle Problem Language Result Execution time Memory
723591 2023-04-14T05:54:59 Z drdilyor Magic Tree (CEOI19_magictree) C++17
34 / 100
 696 ms 1048576 KB 
#include<bits/stdc++.h>

using namespace std;
using ll = long long;


int main() {
    int n, m, k;
    cin >> n >> m >> k;

    vector<vector<int>> child(n);
    vector par(n, -1);
    for (int i = 1; i < n; i++) {
        cin >> par[i];
        child[--par[i]].push_back(i);
    }

    vector<pair<int,int>> fruit(n);
    for (int i =0; i < m;i ++) {
        int v, d, w;
        cin >> v >> d >> w;
        v--;
        fruit[v] = {d, w};
    }


    vector memo(n, vector(k+1, -1ll));
    auto dp = [&](auto& dp, int i, int day)->ll{
        if (day == 0) return 0;
        if (memo[i][day] !=-1) return memo[i][day];
        ll res1 = 0ll;
        if (fruit[i].first == day) res1 += fruit[i].second;
        for (int e : child[i]) {
            res1 += dp(dp, e, day);
        }
        return memo[i][day] = max(res1, dp(dp, i, day-1));
    };
    cout << dp(dp, 0, k) << '\n';
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 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 0 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 696 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 22 ms 8404 KB Output is correct
2 Correct 21 ms 8404 KB Output is correct
3 Correct 21 ms 8432 KB Output is correct
4 Runtime error 487 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 158 ms 10940 KB Output is correct
2 Correct 130 ms 13036 KB Output is correct
3 Correct 141 ms 15904 KB Output is correct
4 Correct 90 ms 11416 KB Output is correct
5 Correct 112 ms 19380 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 1 ms 212 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 0 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 164 ms 24896 KB Output is correct
11 Correct 129 ms 17080 KB Output is correct
12 Correct 144 ms 27824 KB Output is correct
13 Correct 121 ms 23704 KB Output is correct
14 Correct 138 ms 31436 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 398 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 212 KB Output is correct
2 Correct 1 ms 212 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 0 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 22 ms 8404 KB Output is correct
11 Correct 21 ms 8404 KB Output is correct
12 Correct 21 ms 8432 KB Output is correct
13 Runtime error 487 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 212 KB Output is correct
2 Correct 1 ms 212 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 0 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 696 ms 1048576 KB Execution killed with signal 9
11 Halted 0 ms 0 KB -