Submission #1117095

#	Time	Username	Problem	Language	Result	Execution time	Memory
1117095		ortsac	Road Closures (APIO21_roads)	C++17	0 / 100	18 ms	5200 KiB

roads

#include "roads.h"
#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<long long, long long>
#define fr first
#define se second

const int MAXN = 2010;
const int INF = 0x3f3f3f3f3f3f3f3f;
vector<pii> adj[MAXN];
int dp[2][MAXN];
int k;

void dfs(int node, int dad) {
  int pdad = INF;
  for (auto [u, w] : adj[node]) {
    if (u != dad) dfs(u, node);
    else pdad = w;
  }
  // calc dp[0][node] -> edge {node, dad} isn't removed
  if ((k > 0) || (node == 0)) {
    int r = (((int) adj[node].size()) - k);
    vector<int> mini;
    int sum0 = 0;
    for (auto [u, w] : adj[node]) {
      if (u == dad) continue;
      sum0 += dp[0][u];
      mini.push_back(dp[1][u] - dp[0][u]);
    }
    sort(mini.begin(), mini.end());
    int i = 0;
    while ((i < ((int) mini.size())) && ((r > 0) || (mini[i] < 0))) {
      sum0 += mini[i];
      r--;
      i++;
    }
    dp[0][node] = sum0;
  } else {
    dp[0][node] = INF; 
  }
  // calc dp[1][node] -> edge {node, dad} is removed
  int r = (((int) adj[node].size()) - k - 1);
  vector<int> mini;
  int sum0 = pdad;
  for (auto [u, w] : adj[node]) {
    if (u == dad) continue;
    sum0 += dp[0][u];
    mini.push_back(dp[1][u] - dp[0][u]);
  }
  sort(mini.begin(), mini.end());
  int i = 0;
  while ((i < ((int) mini.size())) && ((r > 0) || (mini[i] < 0))) {
    sum0 += mini[i];
    r--;
    i++;
  }
  dp[1][node] = sum0;
}

vector<int> minimum_closure_costs(int32_t n, vector<int32_t> a, vector<int32_t> b, vector<int32_t> w) {
  for (int i = 0; i < (n - 1); i++) {
    adj[a[i]].push_back({b[i], w[i]});
    adj[b[i]].push_back({a[i], w[i]});
  }
  vector<int> ans(n);
  for (int i = 0; i < 2; i++) {
    k = i;
    dfs(0, -1);
    ans[i] = min(dp[0][0], dp[1][0]);
  }
  for (int i = 3; i < n; i++) ans[i] = 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