Submission #939846

#	Time	Username	Problem	Language	Result	Execution time	Memory
939846		duckindog	Race (IOI11_race)	C++17	100 / 100	289 ms	37272 KiB

race

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
 
using namespace std;
 
#ifndef LOCAL
#include "race.h"
#endif
 
const int N = 200'000 + 1;
int n, k;
int answer = 1e7;
vector<pair<int, int>> ad[N];
 
int tsz;
int sz[N];
bool mk[N];
int cnt;
void dfs1(int u, int pre = -1) { 
  sz[u] = 1;
  for (const auto& [v, w] : ad[u]) { 
    if (v == pre || mk[v]) continue;
    dfs1(v, u);
    sz[u] += sz[v];
  }
  tsz = sz[u];
}
 
int dfs2(int u, int pre = -1) { 
  for (const auto& [v, w] : ad[u]) { 
    if (v == pre || mk[v]) continue;
    if (sz[v] > tsz / 2) return dfs2(v, u);
  }
  return u;
}

vector<int> undo;
vector<pair<int, int>> lst;
int d[1'000'010];

int st;
int stage[N];
int sumst[N];
void dfs3(int u, int pre, int dis, int wei) { 
  cnt += 1;
  sumst[st] += 1;
  lst.push_back({dis, wei});
  undo.push_back(wei);
  for (const auto& [v, w] : ad[u]) 
    if (v != pre && !mk[v]) dfs3(v, u, dis + 1, wei + w);
  
}

void dfs4(int u, int pre = -1) { 
  dfs1(u, pre);
  mk[u = dfs2(u, pre)] = true;
  stage[u] = (pre == -1 ? 1 : stage[pre] + 1);
  st = stage[u];
  for (const auto& i : undo) if (i <= k) d[i] = 1e7;
  d[0] = 0;
  undo.clear();
 
  for (const auto& [v, w] : ad[u]) {
    if (v == pre || mk[v]) continue;
    
    lst.clear(); dfs3(v, u, 1, w);
 
    for (const auto& [dis, wei] : lst) if (wei <= k) answer = min(answer, dis + d[k - wei]);
    for (const auto& [dis, wei] : lst) if (wei <= k) d[wei] = min(d[wei], dis);
  }
  
  for (const auto& [v, w] : ad[u]) if (v != pre && !mk[v]) dfs4(v, u);
}
 
int best_path(int a, int b, int h[][2], int l[]) { 
  n = a; k = b;
  for (int i = 0; i < n - 1; ++i) { 
    int u = h[i][0], v = h[i][1], w = l[i];
    ad[u].push_back({v, w});
    ad[v].push_back({u, w});
  }
  memset(d, 40, sizeof d);
  dfs4(0);
  return answer > n ? -1 : answer;
} 
 
#ifdef LOCAL
int h[N][2], l[N];
int32_t main() {
  cin.tie(0)->sync_with_stdio(0);
 
  cin >> n >> k;
  for (int i = 0; i < n - 1; ++i) {
    cin >> h[i][0] >> h[i][1];
    cin >> l[i];
  }
  cout << best_path(n, k, h, l) << "\n";
}
#endif

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