Submission #415822

#	Time	Username	Problem	Language	Result	Execution time	Memory
415822		flashmt	Road Closures (APIO21_roads)	C++17	36 / 100	331 ms	10016 KiB

roads

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

int n;
vector<pair<int, int>> a[100100];
long long f[2020];
long long g[2020]; // can keep parent edge

void visit(int x, int par, int k)
{
  f[x] = 0;
  vector<long long> gain;
  for (auto [y, w] : a[x])
    if (y != par)
    {
      visit(y, x, 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]);
}

vector<long long> minimum_closure_costs(int N, vector<int> U, vector<int> V, vector<int> W) {
  n = N;
  int isLine = 1;
  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]});
    if (U[i] != i || V[i] != i + 1)
      isLine = 0;
  }
  vector<long long> ans(n);
  ans[0] = accumulate(W.begin(), W.end(), 0LL);

  // 1
  if (a[0].size() == n - 1)
  {
    sort(W.begin(), W.end(), greater<int>());
    for (int i = n - 2; i >= 0; i--)
      ans[i] = ans[i + 1] + W[i];
    return ans;
  }

  // 2
  if (isLine)
  {
    vector<long long> f(n, oo);
    f[0] = 0;
    f[1] = W[0];
    for (int i = 2; i < n; i++)
      f[i] = min(f[i - 1], f[i - 2]) + W[i - 1];
    ans[1] = min(f[n - 1], f[n - 2]);
  }

  if (n <= 2000)
  {
    for (int i = 1; i < n - 1; i++)
    {
      visit(0, -1, i);
      ans[i] = f[0];
    }
  }

  return ans;
}

Compilation message (stderr)

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

• Subtask 1: 5 / 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