Submission #1157122

#	Time	Username	Problem	Language	Result	Execution time	Memory
1157122		t9unkubj	Road Closures (APIO21_roads)	C++20	7 / 100	209 ms	63588 KiB

roads

#ifdef t9unkubj

#define _GLIBCXX_DEBUG
#include"debug.cpp"
//#include"template_no_debug.h"
#else 
#include "roads.h"
#define dbg(...) 199958
#endif

#pragma GCC optimize("O3")
using namespace std;
#include<bits/stdc++.h>
using ll=long long;
using ull=unsigned long long;
template<class T>using vc=vector<T>;
template<class T>using vvc=vc<vc<T>>;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,j,n) for(ll i=(j);i<(ll)(n);i++)
#define DREP(i,n,m) for(ll i=(n);i>=(m);i--)
#define drep(i,n) for(ll i=((n)-1);i>=0;i--)
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
template<class T,class F>
bool chmin(T &x, F y){
    if(x>y){
        x=y;
        return true;
    }
    return false;
}
template<class T, class F>
bool chmax(T &x, F y){
    if(x<y){
        x=y;
        return true;
    }
    return false;
}
double pass_time=0;
struct topk{
    multiset<ll>s1,s2;
    int K;
    ll sm;
    topk():K(0),sm(0){}
    void modify(){
        while(s1.size()&&s2.size()&&*s1.rbegin()>*s2.begin()){
            int v1=*s1.rbegin();
            int v2=*s2.begin();
            sm-=v1;
            sm+=v2;
            s1.erase(s1.find(v1)),s2.erase(s2.find(v2));
            s1.insert(v2),s2.insert(v1);
        }
        while((int)s1.size()<K&&(int)s2.size()){
            sm+=*s2.begin();
            s1.insert(*s2.begin());s2.erase(s2.find(*s2.begin()));
        }
        while((int)s1.size()>max(0,K)){
            sm-=*s1.rbegin();
            s2.insert(*s1.rbegin());s1.erase(s1.find(*s1.rbegin()));
        }
    }
    void insert(int x){
        s2.insert(x);
        modify();
    }
    void erase(int x){
        if(s1.find(x)!=s1.end()){
            sm-=x;
            s1.erase(s1.find(x));
        }else{
            if(s2.find(x)!=s2.end()){
                s2.erase(s2.find(x));
            }else assert(0);
        }
        modify();
    }
    void shot(int x){
        K=x;
        modify();
    }
    ll val(){
        if((int)s1.size()>=K)return sm;
        return 2e18;
    }
};
vc<ll>solve(int n,vc<int>u,vc<int>v,vc<int>w){
    ll inf=2e18;
    vc<ll>dp0(n,inf);
    vc<ll>dp1(n,inf);
    vvc<pair<ll,ll>>G(n);
    rep(i,n-1){
        G[u[i]].push_back({v[i],w[i]});
        G[v[i]].push_back({u[i],w[i]}); 
    }

    vvc<int>able(n);
    rep(i,n){
        able[G[i].size()].push_back(i);
    }
    vvc<pair<ll,ll>>g(n);
    vc<topk>topk(n);
    vc<ll>miru;
    vc<int>mita(n);
    rep(i,n){
        for(auto&[to,W]:G[i])topk[i].insert(W),dbg(i,W);
    }
    vc<ll>ans(n);
    drep(i,n){
        for(auto&x:able[i]){
            miru.push_back(x);
            for(auto&[to,W]:G[x]){
                if(pair<int,int>{G[x].size(),x}<pair<int,int>{G[to].size(),to}){
                    g[x].push_back({to,W});
                    g[to].push_back({x,W});
                    topk[x].erase(W);
                    topk[to].erase(W);
                }
            }
        }
        for(auto&x:miru){
            if(mita[x])continue;
            
            auto dfs=[&](auto&dfs,int u,ll from)->void{
                mita[u]=1;
                __int128 offset=0;
                vc<ll>diff;
                for(auto&[to,W]:g[u]){
                    if(mita[to])continue;
                    dfs(dfs,to,W);
                    offset+=dp0[to];
                    diff.push_back({dp1[to]-dp0[to]});
                }
                sort(all(diff));
                {
                ll now=0;
                topk[u].shot((int)G[u].size()-i);
                for(int j=0;;j++){
                    chmin(dp0[u],now+offset+topk[u].val());
                    if(j==diff.size())break;
                    topk[u].shot((int)G[u].size()-i-j-1);
                
                    now+=diff[j];
                }
                }

                if(from>=0)
                {
                ll now=0;
                topk[u].shot((int)G[u].size()-i-1);
                for(int j=0;;j++){
                    chmin(dp1[u],now+offset+topk[u].val());
                    if(j==diff.size())break;
                    topk[u].shot((int)G[u].size()-i-j-2);
                    now+=diff[j];
                }
                }
                if(from!=-1)dp1[u]+=from;
            };
            dfs(dfs,x,-1);
            ans[i]+=dp0[x];
        }
        for(auto&x:miru){
            dp0[x]=dp1[x]=inf;
            mita[x]=0;
        }   
    }
    return ans;
}
std::vector<long long> minimum_closure_costs(int N, std::vector<int> U,
                                             std::vector<int> V,
                                             std::vector<int> W) {
  return solve(N,U,V,W);
}
void run(){
    #ifdef t9unkubj
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
    int n;
    cin>>n;
    vc<int>u(n-1),v(n-1),w(n-1);
    rep(i,n-1)cin>>u[i]>>v[i]>>w[i];
    auto ans=minimum_closure_costs(n,u,v,w);
    dbg(ans);
}
//int main(){run();}

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