Submission #1200052

#	Time	Username	Problem	Language	Result	Execution time	Memory
1200052		ackhava	Road Closures (APIO21_roads)	C++20	12 / 100	338 ms	96028 KiB

roads

#include "roads.h"
#include <bits/stdc++.h>
#define REP(i,o,n) for(long long i=o;i<n;i++)
#define fi first
#define se second
#define pb push_back
using namespace std;

set<pair<long long,long long>> adj[200100];
set<pair<long long,long long>> child[200100];
long long sz[200100];

void dfs(long long node, long long parent=-1){
  sz[node]=1;
  for(auto i:adj[node]){
    if(i.fi!=parent)dfs(i.fi,node),sz[node]+=sz[i.fi],child[node].insert(i);
  }
}

struct ds {
  multiset<long long> select, pool;
  long long lim=0;
  long long sum=0;

  void add(long long x){
    if(x<0 && select.size() < lim)select.insert(x),sum+=x;
    else if(select.size() && x<0 && x < *select.rbegin())sum+=x-*select.rbegin(),pool.insert(*select.rbegin()),select.erase(select.find(*select.rbegin())),select.insert(x);
    else pool.insert(x);
    norm();
  }

  void remove(long long x){
    if(pool.count(x))pool.erase(pool.find(x));
    else {
      select.erase(select.find(x));
      sum-=x;
      norm();
    }
  }

  void norm(){
    while(select.size() < lim && pool.size() && *pool.begin() < 0){
      sum+=*pool.begin();
      select.insert(*pool.begin());pool.erase(pool.begin());
    }

    while(select.size() > lim){
      sum-=*select.rbegin();
      pool.insert(*select.rbegin());
      select.erase(select.find(*select.rbegin()));
    }
  }

  long long query(long long q){
    lim=q;
    norm();
    return sum;
  }
};

ds store[200100];
vector<long long> dead[200100];
bool active[200100];

long long memo[200100][2];
long long bias[200100];

long long dp(long long node, long long k, bool lim){
  auto &ans=memo[node][lim];
  if(ans!=-1)return ans;
  ans=bias[node];
  long long con=k;
  if(lim)con--;
  vector<long long> upgrades;
  for(auto i:child[node]){
    ans+=dp(i.fi,k,false)+i.se;
    upgrades.pb(dp(i.fi,k,true) - (dp(i.fi,k,false)+i.se));
  }
  for(auto i:upgrades)store[node].add(i);
  // cerr<<node<<": ";
  // for(auto i:store[node].select)cerr<<i<<" ";
  // cerr<<"| ";
  // for(auto i:store[node].pool)cerr<<i<<" ";
  // cerr<<endl;
  ans+=store[node].query(con);
  // cerr<<">>> "<<store[node].query(con)<<" "<<ans<<endl;
  for(auto i:upgrades)store[node].remove(i);
  return ans;
}

std::vector<long long> minimum_closure_costs(signed N, std::vector<signed> U,
                                             std::vector<signed> V,
                                             std::vector<signed> W) {
  memset(sz,-1,sizeof sz);
  memset(bias,0,sizeof bias);
  REP(i,0,N)adj[i].clear(),store[i].lim=0,store[i].pool.clear(),store[i].select.clear(),store[i].sum=0,active[i]=1;
  REP(i,0,N-1){
    adj[U[i]].insert({V[i],W[i]});
    adj[V[i]].insert({U[i],W[i]});
  }
  REP(i,0,N)dead[adj[i].size()+2].pb(i);
  dfs(0);
  set<long long> st;
  REP(i,0,N+10)st.insert(i);
  vector<long long> vec;
  REP(i,0,N){
    for(auto d:dead[i]){
      for(auto a:adj[d]){
        child[a.fi].erase({d,a.se});
        adj[a.fi].erase({d,a.se});
        store[a.fi].add(-a.se);
        bias[a.fi]+=a.se;
      }
      st.erase(d);
    }
    for(auto i:st)memo[i][0]=memo[i][1]=-1;
    vec.pb(dp(0,i,false));
    // cerr<<endl;
  }
  return vec;
}

• Subtask 1: 5 / 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