oj.uz

Submission #723590

# Submission time Handle Problem Language Result Execution time Memory
723590 2023-04-14T05:54:22 Z drdilyor Magic Tree (CEOI19_magictree) C++17
22 / 100
 467 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, -1));
    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 300 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 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 418 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 19 ms 4436 KB Output is correct
2 Correct 19 ms 4548 KB Output is correct
3 Correct 20 ms 4436 KB Output is correct
4 Runtime error 467 ms 1048576 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

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

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 300 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 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 151 ms 17984 KB Output is correct
11 Correct 140 ms 14836 KB Output is correct
12 Correct 153 ms 20732 KB Output is correct
13 Correct 117 ms 16444 KB Output is correct
14 Correct 126 ms 24396 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 443 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 300 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 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 19 ms 4436 KB Output is correct
11 Correct 19 ms 4548 KB Output is correct
12 Correct 20 ms 4436 KB Output is correct
13 Runtime error 467 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 300 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 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 418 ms 1048576 KB Execution killed with signal 9
11 Halted 0 ms 0 KB -