Submission #964693

#	Time	Username	Problem	Language	Result	Execution time	Memory
964693		kilkuwu	Road Closures (APIO21_roads)	C++17	0 / 100	2068 ms	23180 KiB

roads

#include "roads.h"

#include <bits/stdc++.h>

std::vector<long long> minimum_closure_costs(int N, std::vector<int> U,
                                             std::vector<int> V,
                                             std::vector<int> W) {


  std::vector<std::vector<std::pair<int, int>>> adj(N);
  long long tot = 0;
  for (int i = 0; i < N - 1; i++) { 
    int u = U[i], v = V[i], w = W[i];
    adj[u].emplace_back(v, w);
    adj[v].emplace_back(u, w);
    tot += w;
  }

  auto solve = [&](int k) -> long long {
    std::vector<std::array<long long, 2>> dp(N, {-1, -1});

    auto dfs = [&](auto self, int u, int p, int s) {
      if (dp[u][s] != -1) return dp[u][s];

      std::vector<std::pair<int, std::pair<int, int>>> options;
      for (auto [v, w] : adj[u]) {
        if (v == p) continue;
        self(self, v, u, 0);
        self(self, v, u, 1);
        options.emplace_back(dp[v][1] - (dp[v][0] + w), std::make_pair(v, w));
      } 

      std::sort(options.begin(), options.end());

      int rem = k - s;

      long long ans = 0;
      for (int i = 0; i < (int) options.size(); i++) {
        int v = options[i].second.first;
        int w = options[i].second.second;
        if (i < rem) {
          ans += dp[v][1];
        } else {
          ans += dp[v][0] + w;
        }
      }

      return dp[u][s] = ans;
    };

    return dfs(dfs, 0, -1, 0);
  };

  std::vector<long long> res(N);
  res[0] = tot;
  res[N - 1] = 0;
  for (int i = N - 2; i >= 1; i--) {
    res[i] = solve(i);
  }
  return res;


  
}

• 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