oj.uz

Submission #723779

# Submission time Handle Problem Language Result Execution time Memory
723779 2023-04-14T09:51:22 Z drdilyor Magic Tree (CEOI19_magictree) C++17
47 / 100
 2000 ms 786436 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 1 ms 296 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 296 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 300 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 2044 ms 11600 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 468 KB Output is correct
4 Execution timed out 2073 ms 26136 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 5436 KB Output is correct
2 Correct 136 ms 7472 KB Output is correct
3 Correct 130 ms 14204 KB Output is correct
4 Correct 95 ms 11448 KB Output is correct
5 Correct 111 ms 23056 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 1 ms 296 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 296 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 300 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 111 ms 5864 KB Output is correct
11 Correct 109 ms 6860 KB Output is correct
12 Correct 109 ms 13528 KB Output is correct
13 Correct 97 ms 24868 KB Output is correct
14 Correct 106 ms 22420 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 1524 KB Output is correct
2 Correct 191 ms 6344 KB Output is correct
3 Correct 184 ms 6192 KB Output is correct
4 Correct 235 ms 6280 KB Output is correct
5 Correct 1273 ms 786436 KB Output is correct
6 Correct 208 ms 8816 KB Output is correct
7 Correct 188 ms 12644 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 1 ms 296 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 296 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 300 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 468 KB Output is correct
13 Execution timed out 2073 ms 26136 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 1 ms 296 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 296 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 300 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Execution timed out 2044 ms 11600 KB Time limit exceeded
11 Halted 0 ms 0 KB -