Submission #1262960

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262960		meisgood	Road Closures (APIO21_roads)	C++20	24 / 100	132 ms	2628 KiB

roads

#include "roads.h"
#include <bits/stdc++.h>
using namespace std ;
#define int long long
vector <pair<int,int>> adj[2003] ;
int dp[2003][2] ;
int nw ;
void dfs(int x,int par){
  int nd=0 ;
  vector <int> v ;
  for (auto [a,l] : adj[x]){
    if (a==par) continue ;
    dfs(a,x) ;
    nd+=min(dp[a][0],dp[a][1]+l) ;
    v.push_back(-min(dp[a][0],dp[a][1]+l)+(dp[a][1]+l)) ;
  }
  sort(v.begin(),v.end()) ;
  if ((int)v.size()>=(int)adj[x].size()-nw){
    dp[x][0]=nd ;
    for (int i = 0 ; i < (int)adj[x].size()-nw ; i ++){
      dp[x][0]+=v[i] ;
    }
  }
  if ((int)v.size()>=(int)adj[x].size()-nw-1){
    dp[x][1]=nd ;
    for (int i = 0 ; i < (int)adj[x].size()-nw-1 ; i ++){
      dp[x][1]+=v[i] ;
    }
  }
  dp[x][1]=min(dp[x][1],dp[x][0]) ;
  // cout << x << " " << dp[x][0] << " " << dp[x][1] << endl ;
}
std::vector<long long> minimum_closure_costs(signed N, std::vector<signed> U,
                                             std::vector<signed> V,
                                             std::vector<signed> W) {
  int i,j ;
  for (i = 0 ; i < N-1 ; i ++){
    adj[U[i]].push_back({V[i],W[i]}) ;
    adj[V[i]].push_back({U[i],W[i]}) ;
  }
  vector <int> ans(N) ;
  for (i = 0 ; i < N ; i ++){
    nw=i ;
    for (j = 0 ; j < N ; j ++) dp[j][0]=dp[j][1]=LLONG_MAX/10000 ;
    dfs(0,-1) ;
    ans[i]=dp[0][0] ;
  }
  return ans;
}
// dp[i][0]=ok
// dp[i][1]=need one more
// dp[i][1]<=dp[i][0]

• 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