Submission #964681

#	Time	Username	Problem	Language	Result	Execution time	Memory
964681		kilkuwu	Road Closures (APIO21_roads)	C++17	7 / 100	62 ms	27696 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<long long> res(N);

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

  std::vector<std::array<long long, 2>> dp(N, {-1, -1});
  res[0] = tot;
  auto dfs = [&](auto self, int u, int p, bool state) -> long long { // state is for Jj
    if (dp[u][state] != -1) return dp[u][state];
    int child = 0;
    long long ans = 1e18;
    for (auto [w, v] : adj[u]) {
      if (v == p) continue;
      child++;
      // now we check it 
      if (state) {
        ans = std::min(ans, w + self(self, v, u, 0)); 
      } else {
        // we can either delete or not 
        auto cand = self(self, v, u, 1);
        auto cand2 = w + self(self, v, u, 0); // disconnect it 
        cand = std::min(cand, cand2);
        ans = std::min(ans, cand);
      }
    }

    if (child == 0) {
      return dp[u][state] = 0;
    } else {
      return dp[u][state] = ans;
    }
  };

  res[1] = dfs(dfs, 0, -1, 0);
  return res;
}

• 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