Submission #1247205

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247205		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;

int used[MAXN], sub[MAXN];

ll dist[MAXN];

map<ll, int> freq;

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){

  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(x == 0){
    if(freq.count(k - dist[v])){
      ans = min(ans, d + freq[k - dist[v]]);
    }
  } else{
    if(freq.count(dist[v])){
      freq[dist[v]] = min(freq[dist[v]], d);
    } else 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;
  freq[0] = 0;

  dist[c] = 0;

  get_dist(c, c);

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

  freq.clear();

  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; 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