Submission #494102

#	Time	Username	Problem	Language	Result	Execution time	Memory
494102		peijar	Road Closures (APIO21_roads)	C++17	0 / 100	2093 ms	11460 KiB

roads

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

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

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

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

      if ((int)adj[v].size() <= maxDeg) {
        swaps.push_back(w);
        continue;
      }

      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 != p);
  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]);
  }

  vector<int> order(N);
  iota(order.begin(), order.end(), 0LL);
  sort(order.begin(), order.end(),
       [&](int i, int j) { return adj[i].size() > adj[j].size(); });

  vector<int> ret(N);
  ret[0] = accumulate(W.begin(), W.end(), 0LL);

  for (int k = 1; k < N; ++k) {
    for (int i = 0; i < N and (int) adj[i].size() > k; ++i)
      if (!seen[i])
        ret[k] += dfs(i, i, k).first;
    for (int i = 0; i < N and (int) adj[i].size() > k; ++i)
      seen[i] = false;
  }

  // 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: 0 / 14
• Subtask 4: 0 / 10
• Subtask 5: 0 / 17
• Subtask 6: 0 / 25
• Subtask 7: 0 / 22