Submission #563825

#	Time	Username	Problem	Language	Result	Execution time	Memory
563825		ian2024	Road Closures (APIO21_roads)	C++14	Compilation error	0 ms	0 KiB

roads

#include <bits/stdc++.h>
#define int long long

using namespace std;

struct C_HASH {
  static uint64_t splitmix64(uint64_t x) {
    // http://xorshift.di.unimi.it/splitmix64.c
    x += 0x9e3779b97f4a7c15;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
    x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
    return x ^ (x >> 31);
  }

  size_t operator()(uint64_t x) const {
    static const uint64_t FIXED_RANDOM =
        chrono::steady_clock::now().time_since_epoch().count();
    return splitmix64(x + FIXED_RANDOM);
  }
};

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
typedef long long ll;

const int INF = 1e9;
const ll INFL = 1e18;
const int MOD = 1000000007;

#define SIZE(a) (int)(a).size()
#define endl '\n'
#define all(x) x.begin(), x.end()
#define ALL(x) begin(x), end(x)

#ifdef LOCAL_PROJECT
std::vector<long long> minimum_closure_costs(int N, std::vector<int> U,
                                             std::vector<int> V,
                                             std::vector<int> W);
signed main() {
  int N;
  assert(1 == scanf("%lld", &N));

  std::vector<int> U(N - 1), V(N - 1), W(N - 1);
  for (int i = 0; i < N - 1; ++i) {
    assert(3 == scanf("%lld %lld %lld", &U[i], &V[i], &W[i]));
  }

  std::vector<long long> closure_costs = minimum_closure_costs(N, U, V, W);
  for (int i = 0; i < static_cast<int>(closure_costs.size()); ++i) {
    if (i > 0) {
      printf(" ");
    }
    printf("%lld", closure_costs[i]);
  }
  printf("\n");
  return 0;
}

#else
#include "roads.h"
#define cerr \
  if (false) cerr
#endif

vector<ii> adj[100005];
int dp[100005][2];
int k;
void dfs(int u, int p) {
  for (auto &[v, w] : adj[u]) {
    if (v == p) {
      continue;
    }
    dfs(v, u);
  }


  int e = SIZE(adj[u]);
  int remove = max(0ll, e - k);
  
  if (remove == 0) {
    dp[u][0] = 0;
    dp[u][1] = 0;
    return;
  }
  
  vector<vector<int> > dp2(e + 1, vector<int>(remove + 1, INFL));
  dp2[0][0] = 0;
  for (int j = 0; j <= remove; ++j) {
    for (int i = 1; i <= e; ++i) {
      if (adj[u][i - 1].first == p) {  // skip over parent
        dp2[i][j] = dp2[i - 1][j];
        continue;
      }

      dp2[i][j] = min(dp2[i - 1][j] + dp[adj[u][i - 1].first][1],
                      dp2[i - 1][j - 1] + dp[adj[u][i - 1].first][0] +
                          adj[u][i - 1].second);
    }
  }

  dp[u][1] = dp2[e][remove];
  dp[u][0] = dp2[e][remove - 1];
}

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) {
    U[i]++;
    V[i]++;
    adj[U[i]].push_back({V[i], W[i]});
    adj[V[i]].push_back({U[i], W[i]});
  }

  vector<int> res(N);
  for (int i = 0; i < N; ++i) {
    for (int j = 0; j <= N; ++j) {
      dp[j][0] = INFL;
      dp[j][1] = INFL;
    }
    k = i;
    dfs(1, 0);
    res[i] = dp[1][1];
  }
  return res;
}

Compilation message (stderr)

roads.cpp: In function 'void dfs(long long int, long long int)':
roads.cpp:71:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   71 |   for (auto &[v, w] : adj[u]) {
      |              ^
/usr/bin/ld: /tmp/ccpeaOCl.o: in function `main':
grader.cpp:(.text.startup+0x26f): undefined reference to `minimum_closure_costs(int, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status