oj.uz

Submission #723781

# Submission time Handle Problem Language Result Execution time Memory
723781 2023-04-14T09:55:01 Z drdilyor Magic Tree (CEOI19_magictree) C++17
47 / 100
 2000 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);
    }
 
    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 = *(dpc.empty() ? new vector<ll>(k+1) : dpc[0]);
        for (int day = 1; day <= k; day++) {
            for (int j = 1; 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 1 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 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 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 Runtime error 1008 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 2 ms 468 KB Output is correct
2 Correct 3 ms 468 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Execution timed out 2085 ms 21304 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 10664 KB Output is correct
2 Correct 125 ms 8504 KB Output is correct
3 Correct 106 ms 11880 KB Output is correct
4 Correct 94 ms 11260 KB Output is correct
5 Correct 111 ms 17824 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 133 ms 15512 KB Output is correct
11 Correct 116 ms 11576 KB Output is correct
12 Correct 108 ms 14764 KB Output is correct
13 Correct 110 ms 25320 KB Output is correct
14 Correct 101 ms 17820 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 63632 KB Output is correct
2 Correct 326 ms 305764 KB Output is correct
3 Correct 311 ms 307944 KB Output is correct
4 Correct 404 ms 397504 KB Output is correct
5 Correct 1920 ms 787884 KB Output is correct
6 Correct 416 ms 477920 KB Output is correct
7 Correct 255 ms 167604 KB Output is correct

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 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 3 ms 468 KB Output is correct
12 Correct 2 ms 468 KB Output is correct
13 Execution timed out 2085 ms 21304 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Runtime error 1008 ms 1048576 KB Execution killed with signal 9
11 Halted 0 ms 0 KB -