Submission #573281

#	Time	Username	Problem	Language	Result	Execution time	Memory
573281		600Mihnea	Road Closures (APIO21_roads)	C++17	31 / 100	2069 ms	52744 KiB

roads

#include <bits/stdc++.h>
#include "roads.h"
 
 
using namespace std;
 
typedef long long ll;
 
vector<ll> minimum_closure_costs(int n, vector<int> Uedges, vector<int> Vedges, vector<int> Wedges) {
  bool is = 0;
  const ll inf = (ll) 1e18 + 7;




  vector<vector<pair<int, int>>> g(n), ginit;
  vector<vector<int>> vertsWithDeg(n);
  vector<int> deg(n, 0);
  vector<ll> sm1(n, 0);
  vector<multiset<ll>> extras1(n), extras2(n);
  vector<ll> dp_take(n), dp_not(n);
  vector<bool> good(n, 1);


  function<void(int, int)> add = [&] (int a, int val) {
    if (extras1[a].empty()) {extras2[a].insert(val); return;}
    if (extras2[a].empty()) {extras1[a].insert(val); sm1[a] += val; return;}
    if (val < *extras2[a].begin()) {
      extras1[a].insert(val);
      sm1[a] += val;
    } else {
      extras2[a].insert(val);
    }
  };

  function<void(int, int)> del = [&] (int a, int val) {
    if (extras1[a].count(val)) {extras1[a].erase(extras1[a].find(val)); sm1[a] -= val; return;}
    if (extras2[a].count(val)) {extras2[a].erase(extras2[a].find(val)); return;}
  };

  function<void(int, int)> percolate = [&] (int a, int dim) {
    while ((int) extras1[a].size() < dim) {
      auto it = extras2[a].begin();
      sm1[a] += *it;
      extras1[a].insert(*it);
      extras2[a].erase(it);
    }
    while ((int) extras1[a].size() > dim) {
      auto it = extras1[a].end();
      it--;
      sm1[a] -= *it;
      extras1[a].erase(it);
      extras2[a].insert(*it);
    }
  };

  int maxDeg;

  vector<int> sub(n), value(n, 0), parrent(n, -1);
  for (int i = 0; i < n - 1; i++) {
    g[Uedges[i]].push_back({Vedges[i], Wedges[i]});
    g[Vedges[i]].push_back({Uedges[i], Wedges[i]});
  }

  ginit = g;

  for (int i = 0; i < n; i++) {
    deg[i] = (int) g[i].size();
    vertsWithDeg[deg[i]].push_back(i);
  }

  for (int root = 0; root < n; root++) {
    sort(g[root].begin(), g[root].end(), [&] (pair<int, int> a, pair<int, int> b) {
        return deg[a.first] > deg[b.first];});
  }

  function<void(int, int)> build = [&] (int a, int p) {
    parrent[a] = p;
    deg[a] = (int) g[a].size();
    sub[a] = 1;
    vector<pair<int, int>> kids;
    for (auto &it : g[a]) {
      int b = it.first;
      if (b == p) continue;
      value[b] = it.second;
      kids.push_back(it);
      build(b, a);
      sub[a] += sub[b];
    }
    g[a] = kids;
  };

  function<void(int)> dfs = [&] (int a) {

    dp_not[a] = dp_take[a] = +inf;

    vector<ll> keks;

    ll sum = 0;

    for (auto &it : g[a]) {
      if (deg[it.first] <= maxDeg) break;
      int b = it.first;
      ll cost = it.second;
      dfs(b);
      sum += dp_not[b];
      ll val = min(0LL, dp_take[b] - dp_not[b]);
      keks.push_back(val);
      add(a, val);
    }


    if (!is) {
      ll s1 = sum;
      ll s2 = sum;

      {
        percolate(a, max(0, maxDeg - 1));
        s2 = sum + sm1[a];
      }

      {
        percolate(a, maxDeg);
        s1 = sum + sm1[a];
      }


      dp_not[a] = s1 + value[a];
      dp_take[a] = s2;
    }

    for (auto &val : keks) {
      del(a, val);
    }
  };

  build(0, -1);

  vector<ll> print(n, 0);
  set<int> goods;
  for (int i = 0; i < n; i++) {
    goods.insert(i);
  }
  ll pay = 0;

  for (maxDeg = 0; maxDeg < n; maxDeg++) {

    for (auto &v : vertsWithDeg[maxDeg]) {
      good[v] = 0;
      goods.erase(v);
      for (auto &it : ginit[v]) {
        int b = it.first, cost = it.second;
        if (good[b] == 0) {
          pay -= cost;
          continue;
        }
        add(b, -cost);
        pay += cost;
      }
    }
    ll sum = pay;

    for (auto &root : goods) {
      if (parrent[root] == -1 || deg[parrent[root]] <= maxDeg) {
        dfs(root);
        sum += dp_not[root] - value[root];
      }
    }
    print[maxDeg] = sum;

  }

 
  return print;
}

Compilation message (stderr)

roads.cpp: In lambda function:
roads.cpp:104:10: warning: unused variable 'cost' [-Wunused-variable]
  104 |       ll cost = it.second;
      |          ^~~~

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