Submission #1082743

#	Time	Username	Problem	Language	Result	Execution time	Memory
1082743		blackslex	Road Closures (APIO21_roads)	C++17	24 / 100	2102 ms	24344 KiB

roads

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

using namespace std;
using ll = long long;
using pii = pair<int, int>;

const int MxN = 25e4 + 5;
ll dp[MxN][2];
vector<pii> v[MxN];

void dfs (int cur, int par, int k) {
    vector<ll> c;
    for (auto &[x, y]: v[cur]) {
        if (par == x) continue;
        dfs(x, cur, k);
        dp[cur][0] += dp[x][1]; dp[cur][1] += dp[x][1];
        c.emplace_back(dp[x][0] + y - dp[x][1]);
    }
    sort(c.rbegin(), c.rend());
    for (int i = 0; i < min(k - 1, (int) c.size()); i++) dp[cur][0] = max(dp[cur][0], dp[cur][0] + c[i]);
    for (int i = 0; i < min(k, (int) c.size()); i++) dp[cur][1] = max(dp[cur][1], dp[cur][1] + c[i]);
}

std::vector<long long> minimum_closure_costs(int N, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
  int n = N, m = U.size();
  ll res = 0;
  for (int i = 0; i < m; i++) v[U[i]].emplace_back(V[i], W[i]), v[V[i]].emplace_back(U[i], W[i]), res += W[i];
  vector<ll> ans;
  for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) dp[j][0] = dp[j][1] = 0;
      dfs(0, -1, i);
      ans.emplace_back(res - dp[0][1]);
  }
  return ans;
}

• 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