제출 #1222789

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1222789		thewizardman	Race (IOI11_race)	C++20	100 / 100	300 ms	42528 KiB

race

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

#define ll long long
#define pll pair<ll, ll>

int sub[200000], K;
bool ct[200000];
vector<pll> adj[200000], vec;
ll dist[200000], mn[1000001], ans;
vector<int> rm;

int dfs(int u, int p) {
  sub[u] = 1;
  for (auto [v, w]: adj[u]) if (v != p && !ct[v]) sub[u] += dfs(v, u);
  return sub[u];
}

int dfs(int u, int p, int n) {
  for (auto [v, w]: adj[u]) if (v != p && !ct[v] && sub[v] > n/2) return dfs(v, u, n);
  return u;
}

void populate_dist(int u, int p, int d) {
  if (dist[u] <= K) vec.push_back({d, dist[u]});
  for (auto [v, w]: adj[u]) if (v != p && !ct[v]) dist[v] = dist[u] + w, populate_dist(v, u, d+1);
}

void build(int u, int p) {
  int n = dfs(u, p);
  int centroid = dfs(u, p, n);
  ct[centroid] = 1;
  // cout << centroid << '\n';
  for (auto [v, w]: adj[centroid]) if (!ct[v]) {
    dist[v] = w; populate_dist(v, centroid, 1);
    // for (auto [de, di]: vec) cout << de << ' ' << di << '\n';
    for (auto [de, di]: vec) ans = min(ans, mn[K-di]+de);
    for (auto [de, di]: vec) mn[di] = min(mn[di], de), rm.push_back(di);
    vec.clear();
  }
  for (auto e: rm) mn[e] = 0x3f3f3f3f;
  rm.clear();
  for (auto [v, w]: adj[centroid]) if (!ct[v]) build(v, centroid);
}

int best_path(int n, int k, int h[][2], int l[]) {
  K = k;
  ans = 0x3f3f3f3f;
  for (int i = 0; i < n-1; i++) {
    adj[h[i][0]].emplace_back(h[i][1], l[i]);
    adj[h[i][1]].emplace_back(h[i][0], l[i]);
  }
  memset(mn, 0x3f, sizeof mn); mn[0] = 0;
  build(0, -1);
  return ans <= 200000 ? ans : -1;
}

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