Submission #1117105

#	Time	Username	Problem	Language	Result	Execution time	Memory
1117105		ortsac	Road Closures (APIO21_roads)	C++17	7 / 100	63 ms	29912 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 = 1e5 + 10;
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;
      if (dp[0][u] < dp[1][u]) {
        sum0 += dp[0][u];
        mini.push_back(dp[1][u] - dp[0][u]);
      } else {
        sum0 += dp[1][u];
        r--;
      }
    }
    sort(mini.begin(), mini.end());
    int i = 0;
    while (r > 0) {
      sum0 += mini[i];
      r--;
      i++;
    }
    dp[0][node] = sum0;
  } else {
    dp[0][node] = INF; 
  }
  // calc dp[1][node] -> edge {node, dad} is removed
  if (node != 0) {
    int r = (((int) adj[node].size()) - k - 1);
    vector<int> mini;
    int sum0 = pdad;
    for (auto [u, w] : adj[node]) {
      if (u == dad) continue;
      if (dp[0][u] < dp[1][u]) {
        sum0 += dp[0][u];
        mini.push_back(dp[1][u] - dp[0][u]);
      } else {
        sum0 += dp[1][u];
        r--;
      }
    }
    sort(mini.begin(), mini.end());
    int i = 0;
    while (r > 0) {
      sum0 += mini[i];
      r--;
      i++;
    }
    dp[1][node] = sum0;
  } else dp[1][node] = INF;
}

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]);
  }
  return ans;
}

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