oj.uz

Submission #896404

# Submission time Handle Problem Language Result Execution time Memory
896404 2024-01-01T11:35:11 Z math_rabbit_1028 Magic Tree (CEOI19_magictree) C++14
37 / 100
 2000 ms 837420 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
int n, m, k, par[101010];
pii arr[101010];
vector<int> adj[101010];
map<int, ll> dp[101010];

ll solve(int v, int d) {
    if (dp[v].find(d) != dp[v].end()) return dp[v][d];
    ll a = 0, b = arr[v].second;
    for (int i = 0; i < adj[v].size(); i++) {
        int u = adj[v][i];
        a += solve(u, d);
        if (arr[v].first >= 1 && arr[v].first <= d) b += solve(u, arr[v].first);
    }
    if (arr[v].first >= 1 && arr[v].first <= d) return dp[v][d] = max(a, b);
    else return dp[v][d] = a;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m >> k;
    for (int i = 2; i <= n; i++) {
        cin >> par[i];
        adj[par[i]].push_back(i);
    }
    for (int i = 1; i <= m; i++) {
        int v, d, w;
        cin >> v >> d >> w;
        arr[v] = {d, w};
    }

    cout << solve(1, k) << "\n";

    return 0;
}

Compilation message

magictree.cpp: In function 'll solve(int, int)':
magictree.cpp:13:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |     for (int i = 0; i < adj[v].size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7516 KB Output is correct
2 Correct 2 ms 7588 KB Output is correct
3 Correct 2 ms 7516 KB Output is correct
4 Correct 2 ms 7516 KB Output is correct
5 Correct 2 ms 7516 KB Output is correct
6 Correct 2 ms 7512 KB Output is correct
7 Correct 2 ms 7516 KB Output is correct
8 Correct 2 ms 7772 KB Output is correct
9 Correct 2 ms 7512 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 16352 KB Output is correct
2 Correct 28 ms 21080 KB Output is correct
3 Correct 56 ms 15584 KB Output is correct
4 Correct 29 ms 15176 KB Output is correct
5 Correct 42 ms 16720 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 20060 KB Output is correct
2 Correct 46 ms 21240 KB Output is correct
3 Correct 44 ms 19788 KB Output is correct
4 Execution timed out 2067 ms 294688 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 22592 KB Output is correct
2 Correct 51 ms 18644 KB Output is correct
3 Correct 61 ms 30176 KB Output is correct
4 Correct 28 ms 17108 KB Output is correct
5 Correct 49 ms 37456 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7516 KB Output is correct
2 Correct 2 ms 7588 KB Output is correct
3 Correct 2 ms 7516 KB Output is correct
4 Correct 2 ms 7516 KB Output is correct
5 Correct 2 ms 7516 KB Output is correct
6 Correct 2 ms 7512 KB Output is correct
7 Correct 2 ms 7516 KB Output is correct
8 Correct 2 ms 7772 KB Output is correct
9 Correct 2 ms 7512 KB Output is correct
10 Correct 255 ms 65104 KB Output is correct
11 Correct 154 ms 51280 KB Output is correct
12 Correct 378 ms 142180 KB Output is correct
13 Correct 32 ms 22564 KB Output is correct
14 Correct 306 ms 149340 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 9820 KB Output is correct
2 Correct 31 ms 19924 KB Output is correct
3 Correct 41 ms 17524 KB Output is correct
4 Correct 31 ms 17492 KB Output is correct
5 Correct 19 ms 21724 KB Output is correct
6 Correct 1930 ms 429928 KB Output is correct
7 Execution timed out 2053 ms 837420 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7516 KB Output is correct
2 Correct 2 ms 7588 KB Output is correct
3 Correct 2 ms 7516 KB Output is correct
4 Correct 2 ms 7516 KB Output is correct
5 Correct 2 ms 7516 KB Output is correct
6 Correct 2 ms 7512 KB Output is correct
7 Correct 2 ms 7516 KB Output is correct
8 Correct 2 ms 7772 KB Output is correct
9 Correct 2 ms 7512 KB Output is correct
10 Correct 39 ms 20060 KB Output is correct
11 Correct 46 ms 21240 KB Output is correct
12 Correct 44 ms 19788 KB Output is correct
13 Execution timed out 2067 ms 294688 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7516 KB Output is correct
2 Correct 2 ms 7588 KB Output is correct
3 Correct 2 ms 7516 KB Output is correct
4 Correct 2 ms 7516 KB Output is correct
5 Correct 2 ms 7516 KB Output is correct
6 Correct 2 ms 7512 KB Output is correct
7 Correct 2 ms 7516 KB Output is correct
8 Correct 2 ms 7772 KB Output is correct
9 Correct 2 ms 7512 KB Output is correct
10 Correct 34 ms 16352 KB Output is correct
11 Correct 28 ms 21080 KB Output is correct
12 Correct 56 ms 15584 KB Output is correct
13 Correct 29 ms 15176 KB Output is correct
14 Correct 42 ms 16720 KB Output is correct
15 Correct 39 ms 20060 KB Output is correct
16 Correct 46 ms 21240 KB Output is correct
17 Correct 44 ms 19788 KB Output is correct
18 Execution timed out 2067 ms 294688 KB Time limit exceeded
19 Halted 0 ms 0 KB -