Submission #1213085

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213085		arman_ferdous	Race (IOI11_race)	C++20	100 / 100	355 ms	31784 KiB

race

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

const int N = 2e5+10;
const int M = 1e6+10;
const int oo = 1e9;

int n, k, ans, table[M];
vector<vector<pair<int,int>>> g;

int sub[N];
bool bad[N];

void dfs_siz (int u, int f) {
  sub[u] = 1;
  for (auto [v, w] : g[u]) if (!bad[v] && v ^ f) dfs_siz(v, u), sub[u] += sub[v];
}

int fc (int u, int f, int lim) {
  for (auto [v, w] : g[u]) if (!bad[v] && v ^ f && sub[v] > lim) return fc(v, u, lim);
  return u;
}

void dfs (int u, int f, int dist, int edgecnt, int ty) {
  if (dist > k) return;
  if (ty == 0) ans = min(ans, table[k - dist] + edgecnt);
  else if (ty == 1) table[dist] = min(table[dist], edgecnt);
  else table[dist] = oo;

  for (auto [v, w] : g[u]) if (!bad[v] && v ^ f)
    dfs(v, u, dist + w, edgecnt + 1, ty);
}

void decompose (int u) {
  dfs_siz(u, 0); u = fc(u, 0, sub[u] >> 1);
  bad[u] = true;

  table[0] = 0;
  for (auto [v, w] : g[u]) if (!bad[v]) {
    dfs(v, u, w, 1, 0);
    dfs(v, u, w, 1, 1);
  }
  table[0] = oo;
  for (auto [v, w] : g[u]) if (!bad[v]) dfs(v, u, w, 1, -1);

  for (auto [v, w] : g[u]) if (!bad[v]) decompose(v);
}

int best_path(int N, int K, int H[][2], int L[]) {
  n = N, k = K;
  g.resize(n);
  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]});
  }
  fill(table, table + k + 1, oo); ans = oo;
  decompose(1);
  if (ans == oo) ans = -1;
  return ans;
}

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