Submission #1112138

#	Time	Username	Problem	Language	Result	Execution time	Memory
1112138		abczz	Road Closures (APIO21_roads)	C++17	Compilation error	0 ms	0 KiB

roads

#include "roads.h"
#include <iostream>
#include <vector>
#include <array>
#include <queue>
#define ll long long

using namespace std;

bool visited[100000], B[100000];
ll f, z, dp[100000][2];
vector <ll> deg[100000];
vector <ll> X, F;
vector <array<ll, 2>> adj[100000];

void dfs(ll u, ll p) {
  visited[u] = 1;
  priority_queue <ll, vector <ll>, greater<ll> > pq;
  ll res = 0;
  for (auto [v, w] : adj[u]) {
    if (v == p) continue;
    if (B[v]) dfs(v, u);
    else dp[v][0] = dp[v][1] = 0;
    res += dp[v][1] + w;
    pq.push(dp[v][0] - dp[v][1] - w);
  }
  for (int i=0; i<z-1; ++i) {
    if (pq.empty()) break;
    auto x = pq.top();
    pq.pop();
    if (x >= 0) break;
    res += x;
  }
  dp[u][0] = res;
  if (z && !pq.empty()) {
    ll x = pq.top();
    if (x < 0) res += x;
  }
  dp[u][1] = res;
}

std::vector<long long> minimum_closure_costs(int N, std::vector<int> U,
                                             std::vector<int> V,
                                             std::vector<int> W) {
  for (int i=0; i<N-1; ++i) {
    adj[U[i]].push_back({V[i], W[i]});
    adj[V[i]].push_back({U[i], W[i]});
  }
  for (int i=0; i<N; ++i) {
    deg[adj[i].size()-1].push_back(i);
  }
  for (int i=N-1; i>=0; --i) {
    z = i, f = 0;
    for (auto u : deg[i]) {
      B[u] = 1;
      X.push_back(u);
    }
    for (auto u : X) visited[u] = 0;
    for (auto u : X) {
      if (!visited[u]) {
        dfs(u, -1);
        f += dp[u][1];
      }
    }
    F.push_back(f);
  }
  reverse(F.begin(), F.end());
  return F;
}

Compilation message (stderr)

roads.cpp: In function 'std::vector<long long int> minimum_closure_costs(int, std::vector<int>, std::vector<int>, std::vector<int>)':
roads.cpp:67:3: error: 'reverse' was not declared in this scope
   67 |   reverse(F.begin(), F.end());
      |   ^~~~~~~