Submission #1154235

#	Time	Username	Problem	Language	Result	Execution time	Memory
1154235		hiderr	Race (IOI11_race)	C++20	21 / 100	3094 ms	12012 KiB

race

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

#define loop(i, a, b) for(int i = a; i <= b; i++)
#define loop_rev(i, a, b) for(int i = a; i >= b; i--)
#define all(x) x.begin(), x.end()
#define sz(x) int(x.size())
#define eb emplace_back
#define pb push_back

using ll = int64_t;

vector<vector<pair<int, int>>> graph;
vector<int> sub, blocked;
int n, k;

void prep_sub(int v, int p) {
  sub[v] = 1;
  for(auto [ s, _ ] : graph[v]) {
    if(s == p || blocked[s]) continue;
    prep_sub(s, v);
    sub[v] += sub[s];
  }
}

int find_centroid(int v, int p) {
  for(auto [ s, _ ] : graph[v]) {
    if(s == p || blocked[s]) continue;
    if(sub[s] > n/2) {
      return find_centroid(s, v);
    }
  }
  return v;
}

constexpr int inf = 1e9;
vector<pair<int, int>> new_distances;
vector<int> all_distances;
vector<int> minim;

void prep_dist(int v, int p, pair<int, int> dist) {
  if(dist.first > k || blocked[v]) return;
  new_distances.pb(dist);
  for(auto [ s, w ] : graph[v]) {
    if(s == p) continue;
    prep_dist(s, v, { dist.first + w, dist.second + 1 });
  }
}

int res = inf;

void solve(int rep) {
  if(blocked[rep]) return;
  prep_sub(rep, (-1));
  int centroid = find_centroid(rep, (-1));
  all_distances = { 0 }, minim[0] = 0;
  for(auto [ s, w ] : graph[centroid]) {
    prep_dist(s, centroid, { w, 1 });
    for(auto [ d, len ] : new_distances) {
      res = min(res, minim[k - d] + len);
    }
    for(auto [ d, len ] : new_distances) {
      minim[d] = min(minim[d], len);
      all_distances.pb(d);
    }
    new_distances.clear();
  }
  for(int d : all_distances) {
    minim[d] = inf;
  }
  all_distances.clear();
  blocked[centroid] = 1;
  for(auto [ s, _ ] : graph[centroid]) {
    solve(s);
  }
}

int best_path(int N, int K, int H[][2], int L[]) {
  n = N, k = K;

  graph.resize(n);
  loop(i, 0, n-2) {
    graph[H[i][0]].pb({ H[i][1], L[i] });
    graph[H[i][1]].pb({ H[i][0], L[i] });
  }

  minim.resize(k + 1, inf);
  blocked.resize(n);
  sub.resize(n);
  solve(0);

  if(res == inf) {
    return (-1);
  }
  else {
    return res;
  }

}

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