Submission #1192753

#	Time	Username	Problem	Language	Result	Execution time	Memory
1192753		Hamed_Ghaffari	Race (IOI11_race)	C++20	100 / 100	382 ms	30532 KiB

race

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

using pii = pair<int, int>;
using ll = long long;

const int MXN = 2e5+5;
const int MXK = 1e6+5;
const int inf = 1e9;

int n, k;
vector<pii> g[MXN];
int ans, mn[MXK];

int sz[MXN];
bool dead[MXN];
int get_sz(int v, int p=-1) {
  sz[v] = 1;
  for(auto [u, w] : g[v])
    if(!dead[u] && u!=p)
      sz[v] += get_sz(u, v);
  return sz[v];
}

int centroid(int v, int N, int p=-1) {
  for(auto [u, w] : g[v])
    if(!dead[u] && u!=p && sz[u]+sz[u]>N)
      return centroid(u, N, v);
  return v;
}

void dfs1(int v, int h=0, ll W=0, int p=-1) {
  if(W<=k) ans = min(ans, mn[k-W]+h);
  for(auto [u, w] : g[v])
    if(!dead[u] && u!=p)
      dfs1(u, h+1, W+w, v);
}
void dfs2(int v, int h=0, ll W=0, int p=-1) {
  if(W<=k) mn[W] = min(mn[W], h);
  for(auto [u, w] : g[v])
    if(!dead[u] && u!=p)
      dfs2(u, h+1, W+w, v);
}
void dfs3(int v, ll W=0, int p=-1) {
  if(W<=k) mn[W] = inf;
  for(auto [u, w] : g[v])
    if(!dead[u] && u!=p)
      dfs3(u, W+w, v);
}

void solve(int v) {
  dead[v = centroid(v, get_sz(v))] = 1;
  mn[0] = 0;
  for(auto [u, w] : g[v])
    if(!dead[u]) {
      dfs1(u, 1, w);
      dfs2(u, 1, w);
    }
  mn[0] = inf;
  for(auto [u, w] : g[v])
    if(!dead[u])
      dfs3(u, w);
  for(auto [u, w] : g[v])
    if(!dead[u])
      solve(u);
}

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]});
  }
  ans = inf;
  fill(mn, mn+k+1, inf);
  solve(0);
  return ans == inf ? -1 : ans;
}

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