oj.uz

Submission #723622

# Submission time Handle Problem Language Result Execution time Memory
723622 2023-04-14T06:31:00 Z drdilyor Magic Tree (CEOI19_magictree) C++17
47 / 100
 2000 ms 786176 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);
    }
 
    map<int,int> comp;
    vector<pair<int,int>> fruit(n);
    for (int i =0; i < m;i ++) {
        ll v, d, w;
        cin >> v >> d >> w;
        v--;
        comp[d] = 0;
        fruit[v] = {d, w};
    }

    k = 0;
    for (auto& mp: comp) mp.second = ++k;
    for (auto& [d, w] : fruit)
        d = comp[d];
 
    auto dp = [&](auto& dp, int i)->vector<ll>{

        vector<vector<ll>> dpc;
        for (int e : child[i])
            dpc.push_back(dp(dp, e));

        vector<ll> res(k+1);
        for (int day = 1; day <= k; day++) {
            for (int j = 0; j < (int)dpc.size(); j++)
                res[day] += dpc[j][day];
            if (day == fruit[i].first)
                res[day] += fruit[i].second;
        }
        int d = fruit[i].first;
        if (d) {
            res[d] = max(res[d], res[d-1]);
            for (int i = d+1; i <= k; i++)
                res[i] = max(res[i], res[d]);
        }
        return res;
    };
    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 0 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 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 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2070 ms 11928 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 2 ms 500 KB Output is correct
4 Execution timed out 2082 ms 26900 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 5436 KB Output is correct
2 Correct 136 ms 5440 KB Output is correct
3 Correct 131 ms 12076 KB Output is correct
4 Correct 102 ms 9656 KB Output is correct
5 Correct 137 ms 21020 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 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 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 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 107 ms 5408 KB Output is correct
11 Correct 121 ms 5440 KB Output is correct
12 Correct 131 ms 11948 KB Output is correct
13 Correct 115 ms 23732 KB Output is correct
14 Correct 117 ms 20908 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 1540 KB Output is correct
2 Correct 202 ms 5656 KB Output is correct
3 Correct 207 ms 5644 KB Output is correct
4 Correct 221 ms 5684 KB Output is correct
5 Correct 1477 ms 786176 KB Output is correct
6 Correct 268 ms 8140 KB Output is correct
7 Correct 204 ms 12136 KB Output is correct

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 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 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 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 2 ms 468 KB Output is correct
11 Correct 2 ms 468 KB Output is correct
12 Correct 2 ms 500 KB Output is correct
13 Execution timed out 2082 ms 26900 KB Time limit exceeded
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 0 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 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 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Execution timed out 2070 ms 11928 KB Time limit exceeded
11 Halted 0 ms 0 KB -