제출 #549136

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
549136		zaneyu	Road Closures (APIO21_roads)	C++14	100 / 100	402 ms	64120 KiB

roads

/*input
6
0 1 915391369
0 2 237972545
0 3 329957228
1 4 112014910
3 5 69344110
*/
#include "roads.h"

#include "roads.h"

#include <cassert>
#include <cstdio>

#include<bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
const int maxn=2e5+5;
#define sz(x) (int)x.size()
#define MNTO(x,y) x=min(x,(__typeof(x))y)
#define pb push_back
const int INF=0x3f3f3f3f;
#define ll long long
#define pii pair<int,int> 
#define f first
#define s second
#define ALL(x) x.begin(),x.end()
set<pii> v[maxn];
ll dp[maxn][2];
int vis[maxn];
struct MS{
    int k;
    multiset<ll> small,big;
    ll sum=0;
    void bal(){
        while(sz(big) and sz(small)<k and (*big.begin())<0){
            sum+=(*big.begin());
            small.insert(*big.begin());
            big.erase(big.begin());
        }
        while(sz(small) and sz(small)>k){
            sum-=(*prev(small.end()));
            big.insert((*prev(small.end())));
            small.erase(prev(small.end()));
        }
    }
    void add(ll x){
        big.insert(x);
        if(sz(small) and (*prev(small.end()))>(*big.begin())){
            ll a=(*big.begin()),b=(*prev(small.end()));
            sum+=a-b;
            big.erase(big.begin());
            small.erase(prev(small.end()));
            big.insert(b),small.insert(a);
        }
    }
    void del(ll x){
        if(small.find(x)!=small.end()){
            sum-=x;
            small.erase(small.find(x));
        }
        else{
            big.erase(big.find(x));
        }
    }
};
int k;
MS ms[maxn];
ll tot[maxn];
inline void dfs(int u,int p){
    vis[u]=k;
    vector<ll> vv;
    ll ans=tot[u];
    for(auto x:v[u]){
        if(x.f==p) continue;
        dfs(x.f,u);
        ll z=dp[x.f][0]-dp[x.f][1]-x.s;
        ms[u].add(z);
        ans+=dp[x.f][1]+x.s;
        vv.pb(z);
    }
    ms[u].k=k-1;
    ms[u].bal();
    dp[u][0]=ans+ms[u].sum;
    ms[u].k=k;
    ms[u].bal();
    dp[u][1]=ans+ms[u].sum;
   // cout<<ms[u].sum<<'\n';
   // for(auto x:ms[u].small) cout<<x<<' ';
    //cout<<u<<' '<<dp[u][0]<<' '<<dp[u][1]<<'\n';
    for(auto x:vv) ms[u].del(x);
}
std::vector<long long> minimum_closure_costs(int N, vector<int> U,vector<int> V,vector<int> W) {
    int n=N;
    vector<pii> vv;
    REP(i,n-1){
        v[U[i]].insert({V[i],W[i]});
        v[V[i]].insert({U[i],W[i]});
    }
    REP(i,n) vv.pb({sz(v[i]),i}),vis[i]=-1;
    sort(ALL(vv));
    reverse(ALL(vv));
    vector<ll> ans(n);
    REP(i,n){
        k=i;
        while(sz(vv) and vv.back().f<=i){
            int z=vv.back().s;
            for(auto x:v[z]){
                tot[x.f]+=x.s;
                ms[x.f].add(-x.s);
                v[x.f].erase({z,x.s});
                    //cout<<i<<' '<<x.f<<' '<<x.s<<'\n';
            }
            vv.pop_back();
        }
        for(auto x:vv){
            ms[x.s].k=i-1;
        }
        for(auto x:vv){
            if(vis[x.s]!=k){
                dfs(x.s,-1);
                ans[i]+=dp[x.s][1];
            }
        }
        //REP(j,n) cout<<j<<' '<<dp[j][0]<<' '<<dp[j][1]<<'\n';
    }
    return ans;
}

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 14 / 14
• Subtask 4: 10 / 10
• Subtask 5: 17 / 17
• Subtask 6: 25 / 25
• Subtask 7: 22 / 22