Submission #1200032

#	Time	Username	Problem	Language	Result	Execution time	Memory
1200032		ackhava	Road Closures (APIO21_roads)	C++20	14 / 100	2097 ms	90900 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;

vector<pair<long long,long long>> adj[200100];
vector<pair<long long,long long>> child[200100];
long long sz[200100];
long long memo[2010][2010][2];

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].pb(i);
  }
}

long long dp(long long node, long long k, bool lim){
  auto &ans=memo[node][k][lim];
  if(ans!=-1)return ans;
  ans=0;
  long long con=k;
  if(lim)con--;
  con=max(con,0LL);
  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));
  }
  sort(upgrades.begin(),upgrades.end());
  REP(i,0,con){
    if(upgrades.size()>i && upgrades[i]<0)ans+=upgrades[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);
  REP(i,0,N)adj[i].clear();
  REP(i,0,N-1){
    adj[U[i]].pb({V[i],W[i]});
    adj[V[i]].pb({U[i],W[i]});
  }
  dfs(0);
  memset(memo,-1,sizeof memo);
  vector<long long> vec;
  REP(i,0,N)vec.pb(dp(0,i,false));
  return vec;
}

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