제출 #717244

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
717244		schiftyfive4	도로 폐쇄 (APIO21_roads)	C++14	100 / 100	206 ms	51772 KiB

roads

#include <bits/stdc++.h>
#include "roads.h"
using namespace std;

#ifdef LOCAL
#include "debug.hpp"
#else
#define debug(...) "MJ >> LAMELO"
#endif

struct kset {
  int n = 1e9;
  multiset<long long, greater<long long>> s;
  long long sum = 0;
  vector<pair<int, long long>> ops;
  void clip(int k) {
    n = k;
    while ((int) s.size() > n) {
      sum -= *s.begin();
      s.erase(s.begin());
    }
  }
  void insert(long long x) {
    sum += x;
    s.insert(x);
    ops.emplace_back(1, x);
    if ((int) s.size() > n) {
      sum -= *s.begin();
      ops.emplace_back(0, *s.begin());
      s.erase(s.begin());
    }
  }
  void rollback() {
    while (!ops.empty()) {
      auto [t, x] = ops.back();
      ops.pop_back();
      if (t == 1) {
        sum -= x;
        assert(s.find(x) != s.end());
        s.erase(s.find(x));
      } else {
        sum += x;
        s.insert(x);
      }
    }
  }
};

std::vector<long long> minimum_closure_costs(int n, std::vector<int> U,
                                             std::vector<int> V,
                                             std::vector<int> W) {
  vector<int> deg(n);
  vector<long long> ans(n);
  vector<vector<pair<int, int>>> g(n);
  for (int i = 0; i < n - 1; i++) {
    ans[0] += W[i];
    deg[U[i]]++; deg[V[i]]++;
    g[U[i]].emplace_back(V[i], W[i]);
    g[V[i]].emplace_back(U[i], W[i]);
  }
  for (int i = 0; i < n; i++) {
    sort(g[i].begin(), g[i].end(), [&](auto u, auto v) {
      return deg[u.first] > deg[v.first];
    });
  }
  vector<int> par(n, -1);
  vector<int> up(n, -1);
  function<void(int, int)> calc = [&](int u, int p) {
    for (auto [v, w] : g[u]) {
      if (v != p) {
        par[v] = u;
        up[v] = w;
        calc(v, u);
      }
    }
  };
  calc(0, -1);
  vector<kset> weights(n);
  vector<vector<long long>> dp(n, vector<long long>(2));
  function<void(int, int, int)> dfs = [&](int u, int p, int k) {
    weights[u].clip(deg[u] - k);
    weights[u].ops.clear();
    long long dp_sum = 0;
    for (auto [v, w] : g[u]) {
      if (v != p) {
        if (deg[v] <= k) {
          break;
        }
        dfs(v, u, k);
        long long mn = min(dp[v][0], dp[v][1]);
        dp_sum += mn;
        weights[u].insert(dp[v][1] - mn);
      }
    }
    assert(!weights[u].s.empty());
    dp[u][0] = dp_sum + weights[u].sum;
    dp[u][1] = dp_sum + weights[u].sum - *weights[u].s.begin() + up[u];
    weights[u].rollback();
  };
  vector<int> big(n);
  iota(big.begin(), big.end(), 0);
  sort(big.begin(), big.end(), [&](int i, int j) {
    return deg[i] > deg[j];
  });
  for (int k = 1; k < n; k++) {
    while (!big.empty()) {
      int u = big.back();
      if (deg[u] > k) {
        break;
      }
      big.pop_back();
      if (u != 0) {
        weights[par[u]].insert(up[u]);
      }
    }
    for (int u : big) {
      if (u == 0 || deg[par[u]] <= k) {
        dfs(u, par[u], k);
        if (u == 0) {
          ans[k] += dp[u][0];
        } else {
          ans[k] += min(dp[u][0], dp[u][1]);
        }
      }
    }
  }
  return ans;
}

컴파일 시 표준 에러 (stderr) 메시지

roads.cpp: In member function 'void kset::rollback()':
roads.cpp:35:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   35 |       auto [t, x] = ops.back();
      |            ^
roads.cpp: In lambda function:
roads.cpp:69:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   69 |     for (auto [v, w] : g[u]) {
      |               ^
roads.cpp: In lambda function:
roads.cpp:84:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   84 |     for (auto [v, w] : g[u]) {
      |               ^

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