Submission #939767

#	Time	Username	Problem	Language	Result	Execution time	Memory
939767		duckindog	Race (IOI11_race)	C++17	21 / 100	3084 ms	22300 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 answer, wei;
vector<pair<int, int>> ad[N];

int tsz;
int sz[N];
bool mk[N];
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> node, undo;
int f[N], dis[N];
int d[1'000'010];
void dfs3(int u, int pre = -1) { 
  node.push_back(u);
  for (const auto& [v, w] : ad[u]) { 
    if (v == pre) continue;
    dis[v] = dis[u] + 1;
    f[v] = f[u] + w;
    dfs3(v, u);
  }
  undo.push_back(f[u]);
}
void clr() { 
  for (const auto& i : undo) if (i <= wei) d[i] = 1e7;
  undo.clear();
}

void dfs4(int u, int pre = -1) { 
  dfs1(u, pre);
  u = dfs2(u, pre);
  mk[u] = true;
  clr();
  // cerr << u << " " << pre << "\n";
  for (const auto& [v, w] : ad[u]) {
    if (v == pre || mk[v]) continue;
    
    node.clear(); 
    f[v] = w; dis[v] = 1;
    dfs3(v, u);

    for (const auto& i : node) if (f[i] <= wei) {
      answer = min(answer, dis[i] + d[wei - f[i]]);
      // if (u == 1) cerr << i << " " << dis[i] << " " << d[wei - f[i]] << "\n";
    }
    for (const auto& i : node) if (f[i] <= wei) d[f[i]] = min(d[f[i]], dis[i]);
  }
  
  for (const auto& [v, w] : ad[u]) if (v != pre && !mk[v]) dfs4(v, u);
}

int best_path(int n, int k, int h[][2], int l[]) { 
  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});
  }
  answer = 1e7; wei = k;
  memset(d, 40, sizeof d); d[0] = 0;
  dfs4(0);
  return answer > n ? -1 : answer;
} 
 
#ifdef LOCAL
#define MAX_AA 500000
static int AA, K;
static int H[MAX_AA][2];
static int L[MAX_AA];
static int solution;
 
#define int long long
mt19937_64 rng(8384815663);
int rnd(int l, int r) { return l + rng() % (r - l + 1); }
 
inline 
void my_assert(int e) {if (!e) abort();}
 
void read_input()
{
  // AA = rnd(2e5, 2e5), K = rnd(100, 100);
  cin >> AA >> K;
  for (int i = 0; i < AA - 1; ++i) { 
    // H[i][0] = rnd(i, i);
    // H[i][1] = i + 1;
    // L[i] = rnd(1, 100);
    cin >> H[i][0] >> H[i][1];
    cin >> L[i];
  }
  solution = -1;
  // cin >> solution;
}
 
int32_t main() {
  int ans;
  read_input();
  ans = best_path(AA,K,H,L);
  cout << ans << "\n";
 
  return 0;
}
#endif

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