Submission #875958

#	Time	Username	Problem	Language	Result	Execution time	Memory
875958		PagodePaiva	Fireworks (APIO16_fireworks)	C++17	0 / 100	24 ms	21696 KiB

fireworks

#include<bits/stdc++.h>
#define N 300010
#define pii pair <int, int>
#define fr first
#define sc second
#define int long long
#define inf 1e18

using namespace std;

int n, m;
vector <pii> gst[N];
vector <pii> g[N];
int vals[N];
vector <int> folhas;
vector <int> tp;
int deg[N], pai[N];
int res[N];

void topsort(){
    queue <int> q;
    for(auto x : folhas) q.push(x);
    deg[1] = -1;

    while(!q.empty()){
        int v = q.front();
        q.pop();
        tp.push_back(v);

        if(v == 1) continue;
        deg[pai[v]]--;
        if(deg[pai[v]] == 0) q.push(pai[v]);
    }
}

void build(int v, int p){
    pai[v] = p;
    deg[v] = gst[v].size();
    for(auto x : gst[v]){
        if(x.fr == p) continue;
        vals[x.fr] = vals[v] + x.sc;
        build(x.fr, v);
    }

    if(gst[v].size() == 0) folhas.push_back(v);

    return;
}

void solve(int v, int val){
    vector <int> stk;
    int p = pai[v];

    for(auto x : g[v]){
        if(x.fr == p) continue;
        stk.push_back(res[x.fr]);
    }

    sort(stk.begin(), stk.end());

    int t = stk.size();

    t = (t-1)/2;

    if(stk.size() % 2 == 0){
        int t1 = 0, t2 = 0;
        int v1 = stk[t], v2 = stk[t+1];

        for(auto x : g[v]){
            if(x.fr == p) continue;
            t1 += abs(res[x.fr] - v1);
            t2 += abs(res[x.fr] - v2);
        }

        t1 += abs(v1);
        t2 += abs(v2);

        if(t1 > t2){
            t++;
        }
    }

    res[v] = stk[t];

    for(auto x : g[v]){
        if(x.fr == p) continue;
        res[x.fr] = res[x.fr] - res[v];
    }

    return;
}

int32_t main(){
    cin >> n >> m;

    for(int i = 2;i <= n+m;i++){
        int a, b;
        cin >> a >> b;
        gst[a].push_back({i, b});
    }
    // cout << '\n';

    build(1, 1);
    topsort();

    int resp = inf;

    for(int val = 0;val <= 90000;val++){
        for(int i = 1;i <= n+m;i++) g[i] = gst[i];
        // int val = vals[x];

        // cout << x << ' ' << val << '\n';

        for(auto v : tp){
            if(g[v].size() == 0) res[v] = val - vals[v];
            else solve(v, val);
            // cout << v << ' ' << res[v] << '\n';
        }

        int sum = 0;

        for(int i = 1;i <= n+m;i++){
            sum += abs(res[i]);
        }

        // cout << sum << '\n';
        // cout << "\n\n\n";
        resp = min(resp, sum);
    }

    cout << resp << '\n';
    return 0;
}

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