oj.uz

Submission #1007620

# Submission time Handle Problem Language Result Execution time Memory
1007620 2024-06-25T09:25:33 Z Hanksburger Fireworks (APIO16_fireworks) C++17
7 / 100
 2 ms 7516 KB 
#include <bits/stdc++.h>
using namespace std;
vector<pair<long long, long long> > child[300005];
long long n, m, ans;
pair<long long, long long> dfs(long long u)
{
    long long sz=child[u].size();
    if (!sz)
        return {0, 0};
    vector<pair<long long, long long> > vec2;
    vector<long long> vec;
    for (long long i=0; i<sz; i++)
    {
        long long v=child[u][i].first, w=child[u][i].second;
        pair<long long, long long> res=dfs(v);
        vec2.push_back({res.first+w, res.second+w});
        vec.push_back(res.first+w);
        vec.push_back(res.second+w);
    }
    sort(vec.begin(), vec.end());
    for (long long i=0; i<sz; i++)
        ans+=max(0LL, max(vec2[i].first-vec[sz], vec[sz]-vec2[i].second));
    return {vec[sz-1], vec[sz]};
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    for (long long i=2; i<=n+m; i++)
    {
        long long p, c;
        cin >> p >> c;
        child[p].push_back({i, c});
    }
    dfs(1);
    cout << ans;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7256 KB Output is correct
2 Correct 1 ms 7260 KB Output is correct
3 Correct 2 ms 7516 KB Output is correct
4 Correct 1 ms 7516 KB Output is correct
5 Correct 1 ms 7260 KB Output is correct
6 Correct 1 ms 7516 KB Output is correct
7 Correct 1 ms 7260 KB Output is correct
8 Correct 1 ms 7500 KB Output is correct
9 Correct 1 ms 7516 KB Output is correct
10 Correct 1 ms 7516 KB Output is correct

Subtask #2
0 / 19.0

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

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7256 KB Output is correct
2 Correct 1 ms 7260 KB Output is correct
3 Correct 2 ms 7516 KB Output is correct
4 Correct 1 ms 7516 KB Output is correct
5 Correct 1 ms 7260 KB Output is correct
6 Correct 1 ms 7516 KB Output is correct
7 Correct 1 ms 7260 KB Output is correct
8 Correct 1 ms 7500 KB Output is correct
9 Correct 1 ms 7516 KB Output is correct
10 Correct 1 ms 7516 KB Output is correct
11 Correct 1 ms 7256 KB Output is correct
12 Correct 2 ms 7256 KB Output is correct
13 Incorrect 1 ms 7260 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7256 KB Output is correct
2 Correct 1 ms 7260 KB Output is correct
3 Correct 2 ms 7516 KB Output is correct
4 Correct 1 ms 7516 KB Output is correct
5 Correct 1 ms 7260 KB Output is correct
6 Correct 1 ms 7516 KB Output is correct
7 Correct 1 ms 7260 KB Output is correct
8 Correct 1 ms 7500 KB Output is correct
9 Correct 1 ms 7516 KB Output is correct
10 Correct 1 ms 7516 KB Output is correct
11 Correct 1 ms 7256 KB Output is correct
12 Correct 2 ms 7256 KB Output is correct
13 Incorrect 1 ms 7260 KB Output isn't correct
14 Halted 0 ms 0 KB -