Submission #740620

#	Time	Username	Problem	Language	Result	Execution time	Memory
740620		amirhoseinfar1385	Road Closures (APIO21_roads)	C++17	100 / 100	308 ms	50428 KiB

roads

#include<bits/stdc++.h>
#include "roads.h"
using namespace std;
const int maxn=100000+10;
struct yal{
    int u,v,w;
    int getad(int fu){
        int ret=(u^v^fu);
        return ret;
    }
};
long long sum=0;
yal alled[maxn];
vector<int>adj[maxn],fake[maxn];
set<int>allrishe;
int n,vis[maxn],len[maxn],par[maxn];
long long dp0[maxn],dp1[maxn],fdp0[maxn],fdp1[maxn];
set<pair<long long,int>>st[maxn],sta[maxn];
set<pair<int,int>>sortlen;

void aval(int u,int lena,int para=-1){
    par[u]=para;
    len[u]=lena;
    for(auto xx:adj[u]){
        int x=alled[xx].getad(u);
        if(xx!=para){
            fake[u].push_back(xx);
            aval(x,lena+1,xx);
        }
    }
}

void del(int u,int i){
    vis[u]=1;
    sortlen.erase(make_pair(-len[u],u));
    allrishe.erase(u);
    if(u!=0){
        if(st[alled[par[u]].getad(u)].count(make_pair(fdp1[u]-fdp0[u],u))!=0){
            dp0[alled[par[u]].getad(u)]-=fdp1[u]-fdp0[u];
            st[alled[par[u]].getad(u)].erase(make_pair(fdp1[u]-fdp0[u],u));
        }
        else{
            sta[alled[par[u]].getad(u)].erase(make_pair(fdp1[u]-fdp0[u],u));
        }
        dp0[alled[par[u]].getad(u)]-=fdp0[u];
        sta[alled[par[u]].getad(u)].insert(make_pair(alled[par[u]].w,u));
    } 
    for(auto xx:fake[u]){
        int x=alled[xx].getad(u);
        if(vis[x]==0){
            allrishe.insert(x);
        }
    }
    for(auto xx:adj[u]){
        int x=alled[xx].getad(u);
        if(vis[x]==1){
            sum-=alled[xx].w;
        }
    }
}

void upd(int u,int i){
    if(u!=0){
        dp0[alled[par[u]].getad(u)]-=fdp0[u];
        long long z=fdp1[u]-fdp0[u];
        if(st[alled[par[u]].getad(u)].count(make_pair(z,u))!=0){
            dp0[alled[par[u]].getad(u)]-=z;
            st[alled[par[u]].getad(u)].erase(make_pair(z,u));
        }
        else{
            sta[alled[par[u]].getad(u)].erase(make_pair(z,u));
        }
    }   
    while((int)sta[u].size()>0&&(int)st[u].size()<i&&(*sta[u].rbegin()).first>0){
        auto x=*sta[u].rbegin();
        sta[u].erase(x);
        st[u].insert(x);
        dp0[u]+=x.first;
    }   
    while((int)sta[u].size()>0&&(int)st[u].size()>0&&(*sta[u].rbegin()).first>(*st[u].begin()).first){
        auto xa=*sta[u].rbegin();
        auto x=*st[u].begin();
        st[u].erase(x);
        sta[u].erase(xa);
        st[u].insert(xa);
        sta[u].insert(x);
        dp0[u]-=x.first;
        dp0[u]+=xa.first;
    }
    if(u!=0&&(int)st[u].size()==i){
        dp1[u]=dp0[u]-(*st[u].begin()).first+alled[par[u]].w;
    }
    else if(u==0){
        dp1[u]=dp0[u];
    }
    else{
        dp1[u]=dp0[u]+alled[par[u]].w;
    }
    if(u!=0){
        sta[alled[par[u]].getad(u)].insert(make_pair(dp1[u]-dp0[u],u));
        dp0[alled[par[u]].getad(u)]+=dp0[u];
        dp1[alled[par[u]].getad(u)]+=dp0[u];
    }
    return ;
}

std::vector<long long> minimum_closure_costs(int N, std::vector<int> U,std::vector<int> V,std::vector<int> W){
    n=N;
    for(int i=0;i<n-1;i++){
        alled[i].u=U[i];
        alled[i].v=V[i];
        alled[i].w=W[i];
        adj[alled[i].u].push_back(i);
        adj[alled[i].v].push_back(i);
        sum+=alled[i].w;
    }
    allrishe.insert(0);
    aval(0,0);
    vector<pair<int,int>>v;
    for(int i=0;i<n;i++){
        v.push_back(make_pair((int)adj[i].size(),i));
        sortlen.insert(make_pair(-len[i],i));
    }
    sort(v.rbegin(),v.rend());
    vector<long long>res(n);
    res[0]=sum;
    for(int i=1;i<=n-1;i++){
        while((int)v.size()>0&&v.back().first<=i){
            del(v.back().second,i);
            v.pop_back();
        }
        for(auto h:sortlen){
            upd(h.second,i);
            fdp0[h.second]=dp0[h.second];
            fdp1[h.second]=dp1[h.second];
        }
        res[i]=sum;
        for(auto x:allrishe){
            if(x==0){
                res[i]-=dp0[x];
            }
            else{
                res[i]-=max(dp0[x],dp1[x]);
            }
        }
    }
    return res;
}

• 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