Submission #1156704

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156704		daoquanglinh2007	Fireworks (APIO16_fireworks)	C++20	7 / 100	3 ms	7492 KiB

fireworks

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pii pair <int, int>
#define fi first
#define se second
#define mp make_pair
#define isz(a) (int)(a).size()

const int NM = 3e5;

int N, M;
vector <pii> adj[NM+5];

pii dfs(int u, int p){
    vector <int> arr = {};
    int res = 0;
    for (pii _ : adj[u]){
        int v = _.fi, c = _.se;
        if (v == p) continue;
        pii tmp = dfs(v, u);
        res += tmp.fi;
        arr.push_back(tmp.se+c);
    }
    if (arr.empty()) return mp(0, 0);
    sort(arr.begin(), arr.end());

    int t = (isz(arr)-1)/2;
    for (int x : arr) res += abs(x-arr[t]);

    return mp(res, arr[t]);
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> M;
    for (int i = 2; i <= N+M; i++){
        int p, c; cin >> p >> c;
        adj[i].push_back(mp(p, c));
        adj[p].push_back(mp(i, c));
    }
    cout << dfs(1, -1).fi;
    return 0;
}

• Subtask 1: 7 / 7
• Subtask 2: 0 / 19
• Subtask 3: 0 / 29
• Subtask 4: 0 / 45