Submission #1117141

#	Time	Username	Problem	Language	Result	Execution time	Memory
1117141		ortsac	Road Closures (APIO21_roads)	C++17	7 / 100	2096 ms	92156 KiB

roads

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

using namespace std;

#define int long long
#define pii pair<long long, long long>
#define fr first
#define se second

struct State {
  int cimaL, node, re;
  State(int a = 0, int b = 0, int c = 0) : cimaL(a), node(b), re(c) {}

  bool operator < (const State& a) const {
    return (make_pair(node, make_pair(cimaL, re)) < make_pair(a.node, make_pair(a.cimaL, a.re)));
  }
};

const int MAXN = 1e5 + 10;
const int INF = 0x3f3f3f3f3f3f3f3f;
vector<pii> adj[MAXN];
map<State, int> dp;
int deg[MAXN];
vector<int> ans;

void calc(int node, int dad) {
  int pdad = INF;
  for (auto [u, w] : adj[node]) {
    if (u != dad) calc(u, node);
    else pdad = w;
  }
  for (int k = 0; k <= deg[node]; k++) {
    // calc dp[0][node] -> edge {node, dad} isn't removed
    if ((k > 0) || (node == 0)) {
      int r = (((int) adj[node].size()) - k);
      vector<int> mini;
      int sum0 = 0;
      for (auto [u, w] : adj[node]) {
        if (u == dad) continue;
        if (deg[u] <= k) {
          if (dp[State(0, u, deg[u])] < dp[State(1, u, deg[u])]) {
            sum0 += dp[State(0, u, deg[u])];
            mini.push_back(dp[State(1, u, deg[u])] - dp[State(0, u, deg[u])]);
          } else {
            sum0 += dp[State(1, u, deg[u])];
            r--;
          }
        } else {
          if (dp[State(0, u, k)] < dp[State(1, u, k)]) {
            sum0 += dp[State(0, u, k)];
            mini.push_back(dp[State(1, u, k)] - dp[State(0, u, k)]);
          } else {
            sum0 += dp[State(1, u, k)];
            r--;
          }
        }
      }
      sort(mini.begin(), mini.end());
      int i = 0;
      while (r > 0) {
        sum0 += mini[i];
        r--;
        i++;
      }
      dp[State(0, node, k)] = sum0;
    } else {
      dp[State(0, node, k)] = INF; 
    }
    // calc dp[1][node] -> edge {node, dad} is removed
    if (node != 0) {
      int r = (((int) adj[node].size()) - k - 1);
      vector<int> mini;
      int sum0 = pdad;
      for (auto [u, w] : adj[node]) {
        if (u == dad) continue;
        if (deg[u] <= k) {
          if (dp[State(0, u, deg[u])] < dp[State(1, u, deg[u])]) {
            sum0 += dp[State(0, u, deg[u])];
            mini.push_back(dp[State(1, u, deg[u])] - dp[State(0, u, deg[u])]);
          } else {
            sum0 += dp[State(1, u, deg[u])];
            r--;
          }
        } else {
          if (dp[State(0, u, k)] < dp[State(1, u, k)]) {
            sum0 += dp[State(0, u, k)];
            mini.push_back(dp[State(1, u, k)] - dp[State(0, u, k)]);
          } else {
            sum0 += dp[State(1, u, k)];
            r--;
          }
        }
      }
      sort(mini.begin(), mini.end());
      int i = 0;
      while (r > 0) {
        sum0 += mini[i];
        r--;
        i++;
      }
      dp[State(1, node, k)] = sum0;
    } else dp[State(1, node, k)] = INF;
  }
}

void dfs(int node, int dad, int mx) {
  if (deg[node] <= mx) {
    for (auto [u, w] : adj[node]) {
      if (u != dad) dfs(u, node, mx); 
    }
    return;
  }
  for (int i = mx + 1; i <= deg[node]; i++) {
    ans[i] += min(dp[State(0, node, i)], dp[State(1, node, i)]);
  }
  mx = deg[node];
  for (auto [u, w] : adj[node]) {
    if (u != dad) dfs(u, node, mx); 
  }
}

vector<int> minimum_closure_costs(int32_t n, vector<int32_t> a, vector<int32_t> b, vector<int32_t> w) {
  for (int i = 0; i < (n - 1); i++) {
    adj[a[i]].push_back({b[i], w[i]});
    adj[b[i]].push_back({a[i], w[i]});
    deg[a[i]]++;
    deg[b[i]]++;
  }
  calc(0, -1);
  ans.resize(n);
  dfs(0, -1, -1);
  return ans;
}

• 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