oj.uz

Submission #896787

# Submission time Handle Problem Language Result Execution time Memory
896787 2024-01-02T06:50:05 Z math_rabbit_1028 Magic Tree (CEOI19_magictree) C++14
21 / 100
 102 ms 37556 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];

void solve(int v) {
    for (int i = 0; i < adj[v].size(); i++) {
        int u = adj[v][i];
        solve(u);
        if (dp[v].size() < dp[u].size()) swap(dp[v], dp[u]);
        for (auto iter = dp[u].begin(); iter != dp[u].end(); iter++) {
            dp[v][iter->first] += iter->second;
        }
    }
    if (arr[v].first == 0) return;
    dp[v][arr[v].first] += arr[v].second;
    auto iter = dp[v].end(); iter--;
    while (iter->first > arr[v].first && arr[v].second > 0) {
        if (iter->second > arr[v].second) {
            iter->second -= arr[v].second;
            arr[v].second = 0;
        }
        else {
            arr[v].second -= iter->second;
            iter = dp[v].erase(iter);
        }
    }
}

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};
    }

    solve(1);

    ll ans = 0;
    for (auto iter = dp[1].begin(); iter != dp[1].end(); iter++) {
        ans += iter->second;
    }

    cout << ans << "\n";

    return 0;
}

Compilation message

magictree.cpp: In function 'void solve(int)':
magictree.cpp:11:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |     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 7516 KB Output is correct
3 Correct 1 ms 7516 KB Output is correct
4 Correct 2 ms 7580 KB Output is correct
5 Correct 3 ms 7516 KB Output is correct
6 Correct 2 ms 7516 KB Output is correct
7 Correct 2 ms 7516 KB Output is correct
8 Correct 3 ms 7516 KB Output is correct
9 Correct 2 ms 7516 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 19024 KB Output is correct
2 Correct 32 ms 19560 KB Output is correct
3 Correct 102 ms 37556 KB Output is correct
4 Correct 54 ms 20544 KB Output is correct
5 Correct 74 ms 22356 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7844 KB Output is correct
2 Incorrect 2 ms 7516 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 16096 KB Output is correct
2 Correct 42 ms 15192 KB Output is correct
3 Correct 36 ms 19280 KB Output is correct
4 Correct 29 ms 16332 KB Output is correct
5 Correct 36 ms 26448 KB Output is correct

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7516 KB Output is correct
2 Correct 2 ms 7516 KB Output is correct
3 Correct 1 ms 7516 KB Output is correct
4 Correct 2 ms 7580 KB Output is correct
5 Correct 3 ms 7516 KB Output is correct
6 Correct 2 ms 7516 KB Output is correct
7 Correct 2 ms 7516 KB Output is correct
8 Correct 3 ms 7516 KB Output is correct
9 Correct 2 ms 7516 KB Output is correct
10 Incorrect 48 ms 18260 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 8280 KB Output isn't correct
2 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 7516 KB Output is correct
3 Correct 1 ms 7516 KB Output is correct
4 Correct 2 ms 7580 KB Output is correct
5 Correct 3 ms 7516 KB Output is correct
6 Correct 2 ms 7516 KB Output is correct
7 Correct 2 ms 7516 KB Output is correct
8 Correct 3 ms 7516 KB Output is correct
9 Correct 2 ms 7516 KB Output is correct
10 Correct 3 ms 7844 KB Output is correct
11 Incorrect 2 ms 7516 KB Output isn't correct
12 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 7516 KB Output is correct
3 Correct 1 ms 7516 KB Output is correct
4 Correct 2 ms 7580 KB Output is correct
5 Correct 3 ms 7516 KB Output is correct
6 Correct 2 ms 7516 KB Output is correct
7 Correct 2 ms 7516 KB Output is correct
8 Correct 3 ms 7516 KB Output is correct
9 Correct 2 ms 7516 KB Output is correct
10 Correct 41 ms 19024 KB Output is correct
11 Correct 32 ms 19560 KB Output is correct
12 Correct 102 ms 37556 KB Output is correct
13 Correct 54 ms 20544 KB Output is correct
14 Correct 74 ms 22356 KB Output is correct
15 Correct 3 ms 7844 KB Output is correct
16 Incorrect 2 ms 7516 KB Output isn't correct
17 Halted 0 ms 0 KB -