Submission #926581

#	Time	Username	Problem	Language	Result	Execution time	Memory
926581		adhityamv	Road Closures (APIO21_roads)	C++17	0 / 100	2050 ms	66252 KiB

roads

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pii pair<ll,ll>
#define fi first
#define se second
const ll INF=1000000000;
const ll K=200000;
ll seg[4*K]={};
ll lazy[4*K]={};
void Build(ll l,ll r,ll pos){
    if(l==r){
        seg[pos]=0;
        lazy[pos]=INF;
        return;
    }
    ll m=(l+r)/2;
    Build(l,m,2*pos);
    Build(m+1,r,2*pos+1);
    seg[pos]=seg[2*pos]+seg[2*pos+1];
    lazy[pos]=INF;
}
void UpdateLazy(ll l,ll r,ll pos){
    if(lazy[pos]==INF) return;
    seg[pos]=(r-l+1LL)*lazy[pos];
    if(l!=r){
        lazy[2*pos]=lazy[pos];
        lazy[2*pos+1]=lazy[pos];
    }
    lazy[pos]=INF;
}
void Update(ll l,ll r,ll pos,ll ql,ll qr,ll qval){
    if(ql>qr) return;
    UpdateLazy(l,r,pos);
    if(ql>r || qr<l) return;
    if(ql<=l && qr>=r){
        lazy[pos]=qval;
        UpdateLazy(l,r,pos);
        return;
    }
    ll m=(l+r)/2;
    Update(l,m,2*pos,ql,qr,qval);
    Update(m+1,r,2*pos+1,ql,qr,qval);
    seg[pos]=(seg[2*pos]+seg[2*pos+1]);
}
ll Query(ll l,ll r,ll pos, ll ql,ll qr){
    if(ql>qr) return 0;
    UpdateLazy(l,r,pos);
    if(ql>r || qr<l) return 0;
    if(ql<=l && qr>=r){
        return seg[pos];
    }
    ll m=(l+r)/2;
    return (Query(l,m,2*pos,ql,qr)+Query(m+1,r,2*pos+1,ql,qr));
}
const ll N=100000;
vector<pii> edges[N];
vector<ll> et;
ll n,m;
ll deg[N];
ll depth[N];
ll focc[N];
ll locc[N];
ll parent[N];
ll upweight[N];
void euler_tour(ll u,ll p){
    parent[u]=p;
    focc[u]=et.size();
    et.push_back(u);
    for(auto v:edges[u]){
        if(v.fi==p) continue;
        depth[v.fi]=depth[u]+1;
        upweight[v.fi]=v.se;
        euler_tour(v.fi,u);
        et.push_back(u);
    }
    locc[u]=et.size()-1;
}
vector<ll> bydeg[N];
multiset<ll> allnums[N];
multiset<ll>  topk[N];
multiset<ll> topk1[N];
ll dp[N];
ll dp1[N];
void dfs(ll u,ll p){
    dp[u]=dp1[u]=0;
    for(auto v:edges[u]){
        if(v.fi==p) continue;
        dfs(v.fi,u);
        allnums[u].insert(upweight[v.fi]+dp1[v.fi]-dp[v.fi]);
        dp[u]+=dp[v.fi];
        dp1[u]+=dp[v.fi];
    }
    auto it=allnums[u].end();
    if(it!=allnums[u].begin()){
        it--;
        topk[u].insert(*it);
        dp[u]+=max(*it,0LL);
        allnums[u].erase(it);
    }
}
ll k=2;
void updatepp(){
    vector<pii> needupdate;
    for(ll i:bydeg[k]) needupdate.push_back(mp(depth[i],i));
    for(ll i:bydeg[k]){
        if(i==0) continue;
        if(deg[parent[i]]>=k) continue;
        needupdate.push_back(mp(depth[parent[i]],parent[i]));
    }
    sort(needupdate.begin(),needupdate.end(),greater<pii>());
    for(auto pa:needupdate){
        ll u=pa.se;
        ll orval=dp[u];
        ll orval1=dp1[u];
        if(topk1[u].size()!=topk[u].size()){
            dp1[u]+=max(*topk[u].begin(),0LL);
            topk1[u].insert(*topk[u].begin());
        }
        if(!allnums[u].empty()){
            auto it=allnums[u].end();
            it--;
            dp[u]+=max(*it,0LL);
            topk[u].insert(*it);
            allnums[u].erase(it);
        }
        ll ex=Query(0,m-1,1,focc[u],locc[u]);
        dp[u]+=ex;
        dp1[u]+=ex;
        if(u==0) continue;
        if(deg[u]<k){
            Update(0,m-1,1,focc[u],locc[u],0);
            Update(0,m-1,1,focc[u],focc[u],dp[u]-orval);
        } else{
            ll p=parent[u];
            ll val=upweight[u]+orval1-orval;
            bool w=false;
            bool w1=false;
            if(topk1[p].find(val)!=topk1[p].end()){
                topk[p].erase(topk[p].find(val));
                topk1[p].erase(topk1[p].find(val));
                dp[p]-=max(val,0LL);
                dp1[p]-=max(val,0LL);
            } else if(topk[p].find(val)!=topk[p].end()){
                 topk[p].erase(topk[p].find(val));
                 dp[p]-=max(val,0LL);
            } else{
                allnums[p].erase(allnums[p].find(val));
            }
            val=upweight[u]+dp1[u]-dp[u];
            topk[p].insert(val);
            dp[p]+=max(val,0LL);
            topk1[p].insert(val);
            dp1[p]+=max(val,0LL);
            if(topk[p].size()>=k){
                auto it=topk[p].begin();
                allnums[p].insert(*it);
                dp[p]-=max(*it,0LL);
                topk[p].erase(it);
            }
            if(topk1[p].size()>=k-1){
                dp1[p]-=max(*topk1[p].begin(),0LL);
                topk1[p].erase(topk1[p].begin());
            }
        }
    }
    Update(0,m-1,1,0,n-1,0);
    k++;
}
vector<ll> minimum_closure_costs(int nn,vector<int> u,vector<int> v,vector<int> w){
    n=nn;
    ll tot=0;
    for(ll i=0;i<n-1;i++){
        edges[u[i]].push_back(mp(v[i],w[i]));
        edges[v[i]].push_back(mp(u[i],w[i]));
        deg[u[i]]++,deg[v[i]]++;
        tot+=w[i];
    }
    depth[0]=0;
    euler_tour(0,-1);
    m=et.size();
    vector<ll> ans;
    ans.push_back(tot);
    dfs(0,-1);
    ans.push_back(tot-dp[0]);
    for(ll i=0;i<n;i++){
        for(ll j=0;j<=deg[i];j++) bydeg[j].push_back(i);
    }
    Build(0,m-1,1);
    while(k<n){
        updatepp();
        ans.push_back(tot-dp[0]);
        break;
    }
    return ans;
}

Compilation message (stderr)

roads.cpp: In function 'void updatepp()':
roads.cpp:156:30: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  156 |             if(topk[p].size()>=k){
      |                ~~~~~~~~~~~~~~^~~
roads.cpp:162:31: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  162 |             if(topk1[p].size()>=k-1){
      |                ~~~~~~~~~~~~~~~^~~~~
roads.cpp:138:18: warning: unused variable 'w' [-Wunused-variable]
  138 |             bool w=false;
      |                  ^
roads.cpp:139:18: warning: unused variable 'w1' [-Wunused-variable]
  139 |             bool w1=false;
      |                  ^~

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