Submission #1007620

#	Time	Username	Problem	Language	Result	Execution time	Memory
1007620		Hanksburger	Fireworks (APIO16_fireworks)	C++17	7 / 100	2 ms	7516 KiB

fireworks

#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 / 7
• Subtask 2: 0 / 19
• Subtask 3: 0 / 29
• Subtask 4: 0 / 45