제출 #1247211

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1247211		julia_08	Race (IOI11_race)	C++20	0 / 100	3 ms	4928 KiB

race

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

using namespace std;

using ll = long long;

const int MAXN = 2e5 + 10;
const int MAXK = 1e6 + 10;

int used[MAXN], sub[MAXN];

ll dist[MAXN];

int freq[MAXN];

vector<pair<int, int>> adj[MAXN];

int ans, k;

int get_size(int v, int p){

  sub[v] = 1;

  for(auto [u, w] : adj[v]){
    if(u == p || used[u]) continue;
    sub[v] += get_size(u, v);
  }

  return sub[v];

}

int get_centroid(int v, int p, int sz){

  for(auto [u, w] : adj[v]){
    if(u == p || used[u]) continue;
    if(sub[u] > sz / 2) return get_centroid(u, v, sz);
  }

  return v;

}

void get_dist(int v, int p){

  if(dist[v] <= k) freq[dist[v]] = 1e9;

  for(auto [u, w] : adj[v]){
    if(u == p || used[u]) continue;
    dist[u] = dist[v] + w;
    get_dist(u, v);
  }

}

void upd_freq(int v, int p, int d, int x){

  if(dist[v] > k) return;

  if(x == 0){
    ans = min(ans, d + freq[k - dist[v]]);
  } else freq[dist[v]] = min(freq[dist[v]], d);

  for(auto [u, w] : adj[v]){
    if(u == p || used[u]) continue;
    upd_freq(u, v, d + 1, x);
  }

}

void build(int v, int p){

  int c = get_centroid(v, p, get_size(v, p));

  used[c] = 1;
  dist[c] = 0;

  get_dist(c, c);
  
  freq[0] = 0;

  for(auto [u, w] : adj[c]){
    if(used[u]) continue;
    upd_freq(u, c, 1, 0);
    upd_freq(u, c, 1, 1);
  }

  get_dist(c, c);

  for(auto [u, w] : adj[c]){
    if(used[u]) continue;
    build(u, c);
  }

}

int best_path(int n, int k_, int h[][2], int l[]){

  k = k_;

  for(int i=0; i<n-1; i++){
    adj[h[i][0] + 1].push_back({h[i][1] + 1, l[i]});
    adj[h[i][1] + 1].push_back({h[i][0] + 1, l[i]});
  }

  ans = 1e9;

  build(1, 1);

  return (ans == 1e9 ? -1 : ans);

}
  

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