Submission #494101

#	Time	Username	Problem	Language	Result	Execution time	Memory
494101		peijar	Road Closures (APIO21_roads)	C++17	24 / 100	229 ms	5064 KiB

roads

#include "roads.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long

const int INF = 1e18;
const int MAXN = 2001;

vector<pair<int, int>> adj[MAXN];

// [withPar, withoutPar]
pair<int, int> dfs(int u, int p, int maxDeg) {
  int coutInit = 0;
  vector<int> swaps;
  for (auto [v, w] : adj[u])
    if (v != p) {

      auto [withPar, withoutPar] = dfs(v, u, maxDeg);

      coutInit += withPar;
      assert(coutInit < INF);
      swaps.push_back(withoutPar + w - withPar);
    }
  sort(swaps.begin(), swaps.end());

  // withPar :
  int toRem = adj[u].size() - maxDeg;
  int withPar = INF;
  if (toRem <= 0)
    withPar = coutInit;
  int accu = coutInit;

  for (int i = 0; i < (int)swaps.size(); ++i) {
    accu += swaps[i];
    if (i + 1 >= toRem)
      withPar = min(withPar, accu);
  }

  // withoutPar
  toRem = adj[u].size() - maxDeg - !!u;
  int withoutPar = INF;
  if (toRem <= 0)
    withoutPar = coutInit;
  accu = coutInit;
  for (int i = 0; i < (int)swaps.size(); ++i) {
    accu += swaps[i];
    if (i + 1 >= toRem)
      withoutPar = min(withoutPar, accu);
  }
  return pair(withPar, withoutPar);
}

vector<int> minimum_closure_costs(signed N, vector<signed> U, vector<signed> V,
                                  vector<signed> W) {

  for (int i = 0; i < N - 1; ++i) {
    adj[U[i]].emplace_back(V[i], W[i]);
    adj[V[i]].emplace_back(U[i], W[i]);
  }

  int tot = accumulate(W.begin(), W.end(), 0LL);
  vector<int> ret(N);
  ret[0] = tot;
  for (int k = 1; k < N; ++k)
    ret[k] = dfs(0, 0, k).first;
  return ret;

  if (U == vector<signed>(N - 1, 0)) {
    vector<int> prefSum(N);
    sort(W.begin(), W.end());
    for (int i = 0; i < N - 1; ++i)
      prefSum[i + 1] = prefSum[i] + W[i];
    reverse(prefSum.begin(), prefSum.end());

    return prefSum;
  }
  return vector<int>(N, 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