Submission #1108160

#	Time	Username	Problem	Language	Result	Execution time	Memory
1108160		keunbum	Race (IOI11_race)	C++14	0 / 100	1 ms	2384 KiB

race

#include "race.h"

#include <bits/stdc++.h>

using namespace std;

int best_path(int N, int K, int H[][2], int L[])
{
  int n = N;
  int k = K;
  vector<vector<pair<int, int>>> g(n);
  for (int i = 0; i < n - 1; ++i) {
    int x = H[i][0];
    int y = H[i][1];
    int z = L[i];
    g[x].emplace_back(y, z);
    g[y].emplace_back(x, z);
  }
  vector<bool> removed(n, false);
  auto GetCenter = [&](int r) {
    vector<int> sz(n);
    vector<int> pv(n);
    auto DFS = [&](auto&& self, int v) -> void {
      sz[v] = 1;
      for (auto [u, _] : g[v]) {
        if (u != pv[v] && !removed[u]) {
          pv[u] = v;
          self(self, u);
          sz[v] += sz[u];
        }
      }
    };
    pv[r] = -1;
    DFS(DFS, r);
    while (true) {
      int nr = -1;
      for (auto [u, _] : g[r]) {
        if (u != pv[r] && !removed[u] && sz[u] * 2 > sz[r]) {
          nr = u;
          break;
        }
      }
      if (nr == -1) {
        return r;
      }
      r = nr;
    }
  };     
  vector<int> dp(k + 1, n);
  auto Find = [&](auto&& self, int v, int pv, int dist, int edges) -> void {
    for (auto [u, w] : g[v]) {
      if (u != pv && dist + w <= k && !removed[u]) {
        dp[dist + w] = min(dp[dist + w], edges + 1);
        dp[k] = min(dp[k], dp[k - w] + 1);
        self(self, u, v, dist + w, edges + 1);
      }
    }
  };
  auto Solve = [&](auto&& self, int v) -> void {
    int c = GetCenter(v);
    removed[c] = true;
    Find(Find, c, -1, 0, 0);
    for (auto [u, _] : g[c]) {
      if (!removed[u]) {
        self(self, u);
      }
    }
  };
  Solve(Solve, 0);
  return (dp[k] == n ? -1 : dp[k]);
}

Compilation message (stderr)

race.cpp: In lambda function:
race.cpp:25:17: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   25 |       for (auto [u, _] : g[v]) {
      |                 ^
race.cpp: In lambda function:
race.cpp:37:17: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   37 |       for (auto [u, _] : g[r]) {
      |                 ^
race.cpp: In lambda function:
race.cpp:51:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   51 |     for (auto [u, w] : g[v]) {
      |               ^
race.cpp: In lambda function:
race.cpp:63:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   63 |     for (auto [u, _] : g[c]) {
      |               ^

• Subtask 1: 0 / 9
• Subtask 2: 0 / 12
• Subtask 3: 0 / 22
• Subtask 4: 0 / 57