Submission #1105632

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105632		Nxmkxing	Race (IOI11_race)	C++14	21 / 100	3058 ms	26440 KiB

race

#include "race.h"
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using pii = pair<int, int>;
const ll inf = 1e18;

const int MxN = 2e5 + 10;
const int MxL = 19;
int n, k, dep[MxN], up[MxN][MxL];
ll dis[MxN];
vector<pii> adj[MxN];

void dfs(int u, int p) {
  for (auto [v, w] : adj[u]) {
    if (v == p) continue;
    dep[v] = dep[u] + 1;
    dis[v] = dis[u] + w;
    up[v][0] = u;
    for (int i = 1; i < MxL; i++) up[v][i] = up[up[v][i-1]][i-1];
    dfs(v, u);
  }
}

int lca(int u, int v) {
  if (dep[u] < dep[v]) swap(u, v);
  int k = dep[u] - dep[v];
  for (int i = 0; i < MxL; i++) if (k & (1 << i)) u = up[u][i];
  if (u == v) return u;
  for (int i = MxL - 1; i >= 0; i--) if (up[u][i] != up[v][i]) u = up[u][i], v = up[v][i];
  return up[u][0];
}

int best_path(int N, int K, int H[][2], int L[])
{
  n = N, k = K;
  for (int i = 0; i < n - 1; i++) {
    int u = H[i][0];
    int v = H[i][1];
    int w = L[i];
    adj[u].push_back({v, w});
    adj[v].push_back({u, w});
  }
  dfs(0, -1);
  ll ans = inf;
  for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
      int l = lca(i, j);
      ll d = dep[i] + dep[j] - dep[l] * 2;
      ll dist = dis[i] + dis[j] - dis[l] * 2;
      if (dist == k) ans = min(ans, d);
    }
  }
  if (ans == inf) return -1;
  return ans;
}

Compilation message (stderr)

race.cpp: In function 'void dfs(int, int)':
race.cpp:16:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   16 |   for (auto [v, w] : adj[u]) {
      |             ^

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