Submission #1215848

#	Time	Username	Problem	Language	Result	Execution time	Memory
1215848		loom	Road Closures (APIO21_roads)	C++20	0 / 100	108 ms	2632 KiB

roads

#include "roads.h"
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define int2 int32_t
#define inf 5e18
#define nl '\n'

const int N = 2000;
vector<pair<int,int>> g[N];
int dp[N][2];

void dfs(int v, int p, int t, int k){
   vector<int> vec;
   int sum = 0;
   
   for(auto [ch, w] : g[v]){
      if(ch == p) continue;

      dfs(ch, v, w, k);
      if(dp[ch][1] != -1) vec.push_back(dp[ch][1] - dp[ch][0]);
      sum += dp[ch][0];
   }

   sort(vec.rbegin(), vec.rend());
   for(int i=0; i < min(k-1, (int)vec.size()); i++) sum += vec[i];

   dp[v][1] = sum + t;
   if(k == 0 and g[v].size() == 0) dp[v][1] = -1;

   if(k-1 < vec.size()) sum += vec[k-1];
   dp[v][0] = sum;
}

vector<int> minimum_closure_costs(int2 n, vector<int2> a, vector<int2> b, vector<int2> w){
   int tot = 0;

   for(int i=0; i<n-1; i++){
      g[a[i]].push_back({b[i], w[i]});
      g[b[i]].push_back({a[i], w[i]});
      tot += w[i];
   }

   vector<int> ans(n);
   for(int i=0; i<n; i++){
      dfs(0, 0, 0, i);
      ans[i] = tot - dp[0][0];
   }
   
   return ans;
}

• 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