Submission #542572

#	Time	Username	Problem	Language	Result	Execution time	Memory
542572		czhang2718	Fireworks (APIO16_fireworks)	C++17	100 / 100	406 ms	129708 KiB

fireworks

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

typedef vector<int> vi;
typedef long long ll;
#define int ll
typedef pair<int, int> pii;
#define pb push_back
#define f first
#define s second
#define sz(x) (int) x.size()
#define rep(i,a,b) for(int i=a; i<=b; i++)

const int N=600001;
int n;
vector<pii> adj[N]; 
multiset<int> s[N];
pair<ll, ll> mb[N]; //mx+b
int par[N];

int find(int x){ return (par[x]==x?x:par[x]=find(par[x])); }

void merge(int x, int y){
    int a=find(x), b=find(y);
    if(sz(s[a])<sz(s[b])) swap(a,b);
    for(int x:s[b]){
        s[a].insert(x);
    }
    mb[a].f+=mb[b].f;
    mb[a].s+=mb[b].s;
    par[b]=a;
}

void dfs(int x, int c){
    if(!sz(adj[x])){
        mb[x]={1, -c};
        s[x]={c, c};
        return;
    }
    for(auto e:adj[x]){
        dfs(e.f, e.s);
        merge(e.f, x);
    }
    x=find(x);
    while(mb[x].f>1){
        int x2=*prev(s[x].end());
        // int x1=*prev(prev(s[x].end()));
        mb[x]={mb[x].f-1, mb[x].s+(ll)x2};
        s[x].erase(--s[x].end());
    }
    int x2=*prev(s[x].end());
    int x1=*prev(prev(s[x].end()));
    s[x].erase(s[x].find(x1)); s[x].erase(s[x].find(x2));
    s[x].insert(x2+c); s[x].insert(x1+c);
    mb[x].s-=ll(c)*mb[x].f;
}

signed main(){
    cin.tie(0)->sync_with_stdio(0);

    int a,b; cin >> a >> b;
    n=a+b;
    rep(i,1,n) par[i]=i;
    rep(i,2,n){
        int par, c; cin >> par >> c;
        adj[par].pb({i, c});
    }
    dfs(1, 0);
    int y=find(1);
    int x=*prev(s[y].end());
    cout << mb[y].f*x+mb[y].s;
}

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