제출 #1317552

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

race

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

typedef long long ll;

#define all(x) (x).begin(), (x).end()
#define isz(x) (int)(x.size())

const int sz = 500200, inf = 1000000000;

struct CentroidDecomposition {
  vector<vector<array<int, 2>>> g;
  vector<int> sz;
  vector<bool> removed;
  vector<vector<array<int, 2>>> dis;
  int n, k, ans;
  CentroidDecomposition(int n, vector<vector<array<int, 2>>> &g, int k) : n(n) , g(g), k(k) {
    removed.assign(n + 1, false);
    sz.assign(n + 1, 0);
    dis.resize(n + 1);
    ans = inf;
  }
  int getSubsize(int u, int p = -1) {
    sz[u] = 1;
    for (auto &[v, w] : g[u])
      if (!removed[v] && v != p) sz[u] += getSubsize(v, u);
    return sz[u];
  }
  int findCentroid(int u, int half, int p = -1) {
    for (auto &[v, w] : g[u]) {
      if (v != p && !removed[v] && sz[v] > half) return findCentroid(v, half, u);
    }
    return u;
  }
  void dfs(int u, int centroid, map<int, int> &mn, int dep = 0, int weight = 0, int p = -1) {
    if (weight > k) return;
    if (mn.count(k - weight))
      ans = min(ans, dep + mn[k - weight]);
    dis[centroid].push_back({dep, weight});
    for (auto &[v, w] : g[u]) {
      if (removed[v] || v == p) continue;
      dfs(v, centroid, mn, dep + 1, weight + w, u);      
    }
  }
  int build(int v = 1) { // TODO inside
    int Subsize = getSubsize(v);
    int centroid = findCentroid(v, Subsize / 2);
    removed[centroid] = true;
    map<int, int> mn;
    mn[0] = 0;
    for (auto &[u, w] : g[centroid]) {
      if (removed[u]) continue;
      dfs(u, centroid, mn, 1, w);
      for (auto [dep, weight] : dis[centroid]) {
        if (mn.count(weight))
          mn[weight] = min(mn[weight], dep);
        else
          mn[weight] = dep;
      }
      dis[centroid].clear();
    }
    for (auto &[u, w] : g[centroid]) {
      if (removed[u]) continue;
      build(u);
    }
    return centroid;
  }
};
int best_path(int N, int K, int H[][2], int L[]) {
  int n = N, k = K;
  vector<vector<array<int, 2>>> g(n + 1);
  for (int i = 0; i < n - 1; i++) {
    H[i][0]++, H[i][1]++;
    g[H[i][0]].push_back({H[i][1], L[i]});
    g[H[i][1]].push_back({H[i][0], L[i]});
  }
  CentroidDecomposition c(n, g, k);
  c.build();
  return (c.ans == inf ? -1 : c.ans); 
}

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