제출 #1124889

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1124889		Mamedov	경주 (Race) (IOI11_race)	C++20	100 / 100	659 ms	40204 KiB

race

#include "race.h"
#include <bits/stdc++.h>

using namespace std;

const int oo = 1e9 + 1;

struct CentroidDecomposition {
  vector<vector<array<int, 2>>>g;
  vector<int>subSize;
  vector<bool>removed;
  vector<int>minDepth;
  int k;
  CentroidDecomposition(int n, int k, vector<vector<array<int, 2>>> &g) : k(k), g(g) {
    subSize.resize(n);
    removed.assign(n, false);
    minDepth.assign(k + 1, oo);
  }
  int getSubSize(int v, int pa = -1) {
    subSize[v] = 1;
    for (auto [to, l] : g[v]) {
      if (to != pa && !removed[to]) subSize[v] += getSubSize(to, v);
    }
    return subSize[v];
  }
  int findCentroid(int v, int halfSize, int pa = -1) {
    for (auto [to, l] : g[v]) {
      if (to != pa && !removed[to] && subSize[to] > halfSize) return findCentroid(to, halfSize, v);
    }
    return v;
  }
  void getDist(int v, int curLen, int depth, vector<array<int, 2>> &dist, int pa) {
    if (curLen > k) return;
    dist.push_back({curLen, depth});
    for (auto [to, l] : g[v]) {
      if (to != pa && !removed[to]) getDist(to, curLen + l, depth + 1, dist, v);
    }
  }
  int shortestKlenPathThroughV(int v) {
    vector<int>all;
    int res = oo;
    minDepth[0] = 0;
    for (auto [to, l] : g[v]) {
      if (!removed[to]) {
        vector<array<int, 2>> dist;
        getDist(to, l, 1, dist, v);
        for (auto [len, depth] : dist) {
          res = min(res, depth + minDepth[k - len]);
        }
        for (auto [len, depth] : dist) {
          minDepth[len] = min(minDepth[len], depth);
          all.push_back(len);
        }
      }
    }
    for (int len : all) {
      minDepth[len] = oo;
    }
    return res;
  }
  int solve(int v = 0) {
    int centroid = findCentroid(v, getSubSize(v) >> 1);
    int res = oo;
    removed[centroid] = true;
    res = min(res, shortestKlenPathThroughV(centroid));

    for (auto [to, l] : g[centroid]) {
      if (!removed[to]) res = min(res, solve(to));
    }
    return res;
  }
};
int best_path(int N, int K, int H[][2], int L[]) {
  vector<vector<array<int, 2>>>g(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]});
  }
  CentroidDecomposition cd(N, K, g);
  int res = cd.solve();
  if (res == oo) res = -1;
  return res;
}

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