Submission #706431

#	Time	Username	Problem	Language	Result	Execution time	Memory
706431		Soumya1	도로 폐쇄 (APIO21_roads)	C++17	100 / 100	440 ms	87184 KiB

roads

#include "roads.h"
#include <bits/stdc++.h>
using namespace std;
const int mxN = 250'005;
using ll = long long;
const ll inf = 1e18;
template <typename T>
struct fenwick {
  vector<T> fenw;
  vector<int> cnt;
  int n;
  fenwick() { }
  fenwick(int _n) : n(_n) {
    fenw.resize(n + 1);
    cnt.resize(n + 1);
  }
  void modify(int x, T v) {
    while (x <= n) {
      fenw[x] += v;
      cnt[x]++;
      x += x & (-x);
    }
  }
  T get(int x) {
    T v{};
    while (x > 0) {
      v += fenw[x];
      x -= x & (-x);
    }
    return v;
  }
  T query(int v) {
    if (v == 0) return 0;
    int idx = 0;
    for (int i = 19; i >= 0; i--) {
      if (idx + (1 << i) <= n && v > cnt[idx + (1 << i)]) {
        v -= cnt[idx + (1 << i)];
        idx += (1 << i);
      }
    }
    if (idx == n) return inf;
    idx++;
    return get(idx);
  }
};
fenwick<ll> ds[mxN];
int deg[mxN];
set<pair<int, int>> ad[mxN];
vector<int> deg_nodes[mxN];
set<int> nodes;
int n;
bool vis[mxN];
int K;
pair<ll, ll> dfs(int u) {
  vis[u] = true;
  priority_queue<ll> pq;
  int childs = 0;
  ll r1 = inf, r2 = inf;
  __int128 cur = 0;
  for (auto [v, w] : ad[u]) {
    if (vis[v]) continue;
    childs++;
    auto [d1, d2] = dfs(v);
    cur += d1;
    pq.push(d1 - d2 - w);
  }
  for (int take = 0; take <= childs; take++) {
    if (take > 0) {
      cur -= pq.top();
      pq.pop();
    }
    if (cur > inf) continue;
    r1 = min(r1, (long long) cur + ds[u].query(max(0, deg[u] - K - take)));
    r2 = min(r2, (long long) cur + ds[u].query(max(0, deg[u] - K - 1 - take)));
  }
  r1 = min(r1, inf);
  r2 = min(r2, inf);
  return {r1, r2};
}
vector<long long> minimum_closure_costs(int N, vector<int> U, vector<int> V, vector<int> W) {
  n = N;
  for (int i = 0; i < n; i++) nodes.insert(i);
  for (int i = 0; i < n - 1; i++) {
    int u = U[i], v = V[i], w = W[i];
    ad[u].insert({v, w});
    ad[v].insert({u, w});
    deg[u]++, deg[v]++;
  }
  vector<pair<int, int>> weight[n];
  for (int i = 0; i < n; i++) {
    deg_nodes[deg[i]].push_back(i);
    weight[i].push_back({-1, -1});
    for (auto [v, w] : ad[i]) weight[i].push_back({w, v});
    sort(weight[i].begin(), weight[i].end());
    ds[i] = fenwick<long long> (deg[i]);
  }
  vector<long long> ans(n);
  for (int k = 0; k < n; k++) {
    K = k;
    for (int u : nodes) {
      if (!vis[u]) {
        ans[k] += dfs(u).first;
      }
    }
    for (int u : nodes) {
      vis[u] = false;
    }
    for (int u : deg_nodes[k]) {
      nodes.erase(u);
      for (auto [v, w] : ad[u]) {
        if (!nodes.count(v)) continue;
        ad[v].erase({u, w});
        int idx = lower_bound(weight[v].begin(), weight[v].end(), make_pair(w, u)) - weight[v].begin();
        ds[v].modify(idx, w);
      }
    }
  }
  return ans;
}

• 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