Submission #573167

#	Time	Username	Problem	Language	Result	Execution time	Memory
573167		600Mihnea	Road Closures (APIO21_roads)	C++17	14 / 100	2085 ms	1048576 KiB

roads

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


using namespace std;

typedef long long ll;

vector<ll> minimum_closure_costs(int n, vector<int> Uedges, vector<int> Vedges, vector<int> Wedges) {

  const ll inf = (ll) 1e18 + 7;

  assert((int) Uedges.size() == n - 1);
  assert((int) Vedges.size() == n - 1);
  assert((int) Wedges.size() == n - 1);

  vector<vector<pair<int, int>>> g(n);
  vector<ll> dp_take(n, -inf);
  vector<ll> dp_not(n, -inf);

  int maxDeg;

  vector<int> sub(n), value(n, 0);
  for (int i = 0; i < n - 1; i++) {
    g[Uedges[i]].push_back({Vedges[i], Wedges[i]});
    g[Vedges[i]].push_back({Uedges[i], Wedges[i]});
  }

  function<void(int, int)> build = [&] (int a, int p) {
    sub[a] = 1;
    vector<pair<int, int>> kids;
    for (auto &it : g[a]) {
      int b = it.first;
      if (b == p) continue;
      value[b] = it.second;
      kids.push_back(it);
      build(b, a);
      sub[a] += sub[b];
    }
    g[a] = kids;
  };

  function<void(int)> dfs = [&] (int a) {
    if (g[a].empty()) {
      dp_not[a] = 0;
      if (1 <= maxDeg) {
        dp_take[a] = value[a];
      }
      return;
    }

    assert(!g[a].empty());

    vector<ll> best(n, -inf);
    best[0] = 0;

    for (auto &it : g[a]) {
      int b = it.first;
      ll cost = it.second;
      dfs(b);


      vector<ll> new_best(n, -inf);

      for (int bef = 0; bef < n; bef++) {
        /// don't take it
        new_best[bef] = max(new_best[bef], best[bef] + dp_not[b]);
        /// take it
        if (bef + 1 < n) {
          new_best[bef + 1] = max(new_best[bef + 1], best[bef] + dp_take[b]);
        }
      }
      best = new_best;
    }

    for (int d = 0; d <= maxDeg; d++) {
      dp_not[a] = max(dp_not[a], best[d]);
      if (d + 1 <= maxDeg) {
        dp_take[a] = max(dp_take[a], best[d] + value[a]);
      }
    }

  };

  build(0, -1);

  vector<ll> print(n, 0);

  for (maxDeg = 0; maxDeg < n; maxDeg++) {
    for (auto &x : dp_take) x = -inf;
    for (auto &x : dp_not) x = -inf;
    dfs(0);
    print[maxDeg] = dp_not[0];
  }

  ll totalSum = 0;
  for (auto &x : Wedges) {
    totalSum += x;
  }

  for (auto &x : print) {
    x = totalSum - x;
  }

  return print;
}

Compilation message (stderr)

roads.cpp: In lambda function:
roads.cpp:59:10: warning: unused variable 'cost' [-Wunused-variable]
   59 |       ll cost = it.second;
      |          ^~~~

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