Submission #1128656

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128656		VinhLuu	Race (IOI11_race)	C++17	100 / 100	331 ms	55556 KiB

race

#include <bits/stdc++.h>
#define ll long long
#define all(lpv) lpv.begin(), lpv.end()
#define pot(x, y) lower_bound(x.begin(), x.end(), y) - x.begin() + 1
using namespace std;

//#define lpv

#ifndef lpv
#include "race.h"
#endif // lpv

//#define int long long

const int N = 1e6 + 5;

int ans, n, k, dp[N], sum, cent, sub[N];
ll d[N];
vector<pair<int,int>> p[N];
bool del[N];
const int oo = 1e9;

void pre(int u,int v) {
  sub[u] = 1;
  sum++;
  for(auto ptr : p[u]) {
    int j, w; tie(j, w) = ptr;
    if(j == v || del[j]) continue;
    pre(j, u);
    sub[u] += sub[j];
  }
}

int FIND(int u,int v) {
  for(auto ptr : p[u]) {
    int j, w; tie(j, w) = ptr;
    if(del[j] || j == v) continue;
    if(sub[j] > sum / 2) return FIND(j, u);
  }
  return u;
}

vector<int> collect;
vector<pair<int,int>> vr;

void sol(int u,int v, int edge) {
  if(d[u] > k) return;
  collect.push_back(d[u]);
  vr.push_back({d[u], edge});
  ans = min(ans, edge + dp[k - d[u]]);
//  cerr << u << " " << v << " " << edge << " " << d[u] << " " << dp[k - d[u]] << " t\n";
  for(auto ptr : p[u]) {
    int j, w; tie(j, w) = ptr;
    if(j == v || del[j]) continue;
    d[j] = d[u] + w;
    sol(j, u, edge + 1);
  }
}

void cen(int u) {
  sum = 0;
  pre(u, 0);
  cent = FIND(u, 0);
  del[cent] = 1;

  d[cent] = 0;
  dp[0] = 0;
  collect.clear();
  collect.push_back(0);
  for(auto ptr : p[cent]) {
    int j, w; tie(j, w) = ptr;
    if(del[j]) continue;
    vr.clear();
    d[j] = d[cent] + w;
    sol(j, u, 1);
    for(auto tmp : vr) {
      int x, y; tie(x, y) = tmp;
      dp[x] = min(dp[x], y);
    }
  }

//  cerr << cent << " t\n";
//  for(auto j : collect) cerr << j << " ";
//  cerr << "\n";

  for(auto j : collect) dp[j] = oo;

  for(auto ptr : p[cent]) {
    int j, w; tie(j, w) = ptr;
    if(del[j]) continue;
    cen(j);
  }
}

void dfs(int u,int v,int edge,ll wet) {
  if(wet == k) ans = min(ans, edge);
  for(auto ptr : p[u]) {
    int j, w; tie(j, w) = ptr;
    if(j == v) continue;
    dfs(j, u, edge + 1, wet + w);
  }
}

int best_path(int _n, int _k, int H[][2], int L[]) {
  n = _n, k = _k;
  ans = n;
  for(int i = 1; i < n; i ++) {
    int x = H[i - 1][0] + 1, y = H[i - 1][1] + 1, c = L[i - 1];
//    cerr << x << " " << y << " " << c << " f\n";
    p[x].push_back({y, c});
    p[y].push_back({x, c});
  }


  if(n <= 1000) for(int i = 1;i <= n; i ++) dfs(i, 0, 0, 0);
  else {
    for(int i = 0; i <= k; i ++) dp[i] = oo;
    cen(1);
  }
//  cerr << ans << " result\n";
  return (ans == n ? -1 : ans);
}


#ifdef lpv
int h[N][2], l[N];
signed main() {
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  #define task "v"
  if(fopen(task ".inp","r")) {
    freopen(task ".inp","r",stdin);
    freopen(task ".out","w",stdout);
  }

  int _n, _k; cin >> _n >> _k;

  for(int i = 1; i < _n; i ++) {
    cin >> h[i - 1][0] >> h[i - 1][1] >> l[i - 1];
  }

  cout << best_path(_n, _k, h, l);


}

#endif // lpv

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