Submission #982174

#	Time	Username	Problem	Language	Result	Execution time	Memory
982174		vjudge1	Road Closures (APIO21_roads)	C++17	24 / 100	1033 ms	6812 KiB

roads

#include "roads.h"
#define _GLIBCXX_DEBUG 1
#pragma GCC optimize "O3,unroll-loops,trapv"
#include <bits/stdc++.h>
#define REP(i,o,n) for(int i=o;i<n;i++)
#define FORI(v) for(auto i:v)
#define FORJ(v) for(auto j:v)
#define FORK(v) for(auto i:v)
#define fi first
#define se second
#define pb push_back
using namespace std;
using pii = pair<int,int>;

long long memo[3000][3];
int k;

vector<pii> adj[3000];

long long dp(int node, int parent, bool shadow){
  if(shadow && k==0)return 1e18;
  if(adj[node].size()==1 && (parent != -1))return 0;
  long long &ans=memo[node][shadow];
  if(ans!=-1)return ans;
  ans = 0;
  vector<int> addgains;
  FORI(adj[node]){
    if(i.fi==parent)continue;
    ans += dp(i.fi, node, false) + i.se;
    addgains.pb(dp(i.fi,node,true) - (dp(i.fi, node, false) + i.se));
  }
  sort(addgains.begin(), addgains.end());
  int limit = k;
  if(shadow)limit--;
  limit=min<int>(addgains.size(), limit);
  REP(i,0,limit){
    if(addgains[i]>0)break;
    ans += addgains[i];
  }
  return ans;
}

std::vector<long long> minimum_closure_costs(int N, std::vector<int> U,
                                             std::vector<int> V,
                                             std::vector<int> W) {
  REP(i,0,N-1){
    adj[U[i]].pb({V[i], W[i]});
    adj[V[i]].pb({U[i], W[i]});
  }
  
  vector<long long>ans;

  REP(i,0,N){
    memset(memo,-1,sizeof memo);
    k = i;
    ans.pb(dp(0,-1,0));
    ans.pb(dp(0,-1,true));
    ans.pop_back();
    // cerr<<"=== k="<<i<<" ===\n";
    // REP(j,0,N)cerr<<j<<": "<<memo[j][0]<<" / "<<memo[j][1]<<'\n';
    // cerr<<endl<<endl;
  }
  return ans;
}

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