oj.uz

Submission #723618

# Submission time Handle Problem Language Result Execution time Memory
723618 2023-04-14T06:24:47 Z drdilyor Magic Tree (CEOI19_magictree) C++17
34 / 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];
 
    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 res = 0ll;
        if (fruit[i].first == day) res += fruit[i].second;
        for (int e : child[i]) {
            res += dp(dp, e, day);
        }
        if (fruit[i].first) {
            if (day > fruit[i].first)
                res = max(res, dp(dp, i, fruit[i].first));
            else if (day == fruit[i].first)
                res = max(res, dp(dp, i, fruit[i].first-1));
        }
        return memo[i][day] = res;
    };
    cout << dp(dp, 0, k) << '\n';
    int bad = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 1; j <= k; j++)
            bad += memo[i][j] == -1;
    }
    cerr << n*k - bad << ' ' << bad / double(n * 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 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 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 458 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 7 ms 3544 KB Output is correct
2 Correct 9 ms 3540 KB Output is correct
3 Correct 7 ms 3596 KB Output is correct
4 Runtime error 492 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 134 ms 10956 KB Output is correct
2 Correct 134 ms 12968 KB Output is correct
3 Correct 126 ms 17576 KB Output is correct
4 Correct 95 ms 11360 KB Output is correct
5 Correct 119 ms 23916 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 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 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 208 ms 24940 KB Output is correct
11 Correct 149 ms 17212 KB Output is correct
12 Correct 157 ms 29700 KB Output is correct
13 Correct 94 ms 23808 KB Output is correct
14 Correct 151 ms 35916 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 125908 KB Output is correct
2 Correct 367 ms 606488 KB Output is correct
3 Correct 364 ms 609612 KB Output is correct
4 Correct 433 ms 788084 KB Output is correct
5 Correct 406 ms 786504 KB Output is correct
6 Correct 1544 ms 791228 KB Output is correct
7 Execution timed out 2095 ms 794224 KB Time limit exceeded
8 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 0 ms 212 KB Output is correct
3 Correct 1 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 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 7 ms 3544 KB Output is correct
11 Correct 9 ms 3540 KB Output is correct
12 Correct 7 ms 3596 KB Output is correct
13 Runtime error 492 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 0 ms 212 KB Output is correct
3 Correct 1 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 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 458 ms 1048576 KB Execution killed with signal 9
11 Halted 0 ms 0 KB -