Submission #1129609

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129609		viwlesxq	Race (IOI11_race)	C++20	43 / 100	259 ms	115428 KiB

race

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 1;
const int inf = 1e9;

int d[N], dp[N], up[N][18];
int tin[N], tout[N], timer;
vector<array<int, 2>> g[N];

vector<vector<int>> dp100(N, vector<int> (101, inf));

int n, k, res = inf;

void dfs(int v, int p = 0) {
  tin[v] = ++timer;

  up[v][0] = p;
  for (int i = 1; i < 18; ++i)
    up[v][i] = up[up[v][i - 1]][i - 1];

  for (auto [to, w] : g[v]) {
    if (to != p) {
      d[to] = d[v] + 1;
      dp[to] = dp[v] + w;
      dfs(to, v);
    }
  }

  tout[v] = ++timer;
}

bool upper(int u, int v) {
  return tin[u] <= tin[v] && tout[u] >= tout[v];
}

int lca(int u, int v) {
  if (upper(u, v)) return u;
  if (upper(v, u)) return v;

  for (int i = 17; i >= 0; --i)
    if (!upper(up[u][i], v))
      u = up[u][i];

  return up[u][0];
}

int get(int u, int v) {
  int p = lca(u, v);
  if (dp[u] + dp[v] - 2 * dp[p] == k)
    return d[u] + d[v] - 2 * d[p];
  return inf;
}

void dfs100(int v, int p) {
  dp100[v][0] = 0;

  for (auto [to, w] : g[v]) {
    if (to != p) {
      dfs100(to, v);
      for (int i = 0; i + w <= k; ++i)
        res = min(res, dp100[to][i] + dp100[v][k - i - w] + 1);
      for (int i = 0; i + w <= k; ++i)
        dp100[v][i + w] = min(dp100[v][i + w], dp100[to][i] + 1);
    }
  }

  res = min(res, dp100[v][k]);
}

int best_path(int N, int K, int h[][2], int l[]) {
  n = N, k = K;

  for (int i = 0; i < n - 1; ++i) {
    g[h[i][0]].push_back({h[i][1], l[i]});
    g[h[i][1]].push_back({h[i][0], l[i]});
  }

  if (n <= 1000) {
    dfs(0);

    for (int i = 0; i < n; ++i)
      for (int j = i + 1; j < n; ++j)
        res = min(res, get(i, j));

  } else {
    dfs100(0, -1);
  }

  return res < inf ? res : -1;
}

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