Submission #415882

#	Time	Username	Problem	Language	Result	Execution time	Memory
415882		flashmt	Road Closures (APIO21_roads)	C++17	24 / 100	370 ms	20924 KiB

roads

#include <bits/stdc++.h>
using namespace std;
const long long oo = 1LL << 60;

int n, preDfs[100100], postDfs[100100], dfsTime, deg[100100], curDeg[100100], par[100100];
vector<pair<int, int>> a[100100];
long long f[100100];
long long g[100100]; // can keep parent edge
vector<int> nodes[100100];

void visit(int x, int k)
{
  f[x] = 0;
  vector<long long> gain;
  for (auto [y, w] : a[x])
    if (y != par[x])
    {
      visit(y, k);
      f[x] += f[y] + w;
      gain.push_back(g[y] - f[y] - w);
    }

  sort(gain.begin(), gain.end());
  g[x] = f[x];
  for (int i = 0; i < k && i < gain.size(); i++)
  {
    if (gain[i] >= 0)
      break;
    f[x] += gain[i];
    if (i < k - 1)
      g[x] += gain[i];
  }
  f[x] = min(f[x], g[x]);
}

void dfs(int x)
{
  preDfs[x] = ++dfsTime;
  for (auto [y, _] : a[x])
    if (y != par[x])
    {
      par[y] = x;
      dfs(y);
    }
  postDfs[x] = dfsTime;
}

int solve(int k, set<pair<int, int>> &nodes)
{
  for (auto [_, x] : nodes)
    curDeg[x] = deg[x];
  int res = 0;
  for (auto [_, x] : nodes)
    if (curDeg[x] > k)
    {
      res += curDeg[x] - k;
      if (par[x] >= 0)
        curDeg[par[x]]--;
    }
  return res;
}

vector<long long> minimum_closure_costs(int N, vector<int> U, vector<int> V, vector<int> W) {
  n = N;
  int isWeighted = 0;
  for (int i = 0; i < n - 1; i++)
  {
    a[U[i]].push_back({V[i], W[i]});
    a[V[i]].push_back({U[i], W[i]});
    deg[U[i]]++;
    deg[V[i]]++;
    if (W[i] > 1)
      isWeighted = 1;
  }
  for (int i = 0; i < n; i++)
    nodes[deg[i]].push_back(i);

  set<int> allDegs;
  vector<long long> ans(n);
  ans[0] = accumulate(W.begin(), W.end(), 0LL);

  dfsTime = 0;
  par[0] = -1;
  dfs(0);

  if (n <= 2000)
  {
    for (int i = 1; i < n - 1; i++)
    {
      visit(0, i);
      ans[i] = f[0];
    }
  }
  else if (!isWeighted)
  {
    set<pair<int, int>> s;
    for (int i = 0; i < n; i++)
      s.insert({-preDfs[i], i});
    for (int i = 1; i < n - 1; i++)
    {
      if (nodes[i].empty()) ans[i] = ans[i - 1];
      else
      {
        for (int x : nodes[i])
          s.erase({-preDfs[x], x});
        ans[i] = solve(i, s);
      }
    }
  }

  return ans;
}

Compilation message (stderr)

roads.cpp: In function 'void visit(int, int)':
roads.cpp:25:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |   for (int i = 0; i < k && i < gain.size(); i++)
      |                            ~~^~~~~~~~~~~~~

• 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