Submission #1096000

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096000		YugiHacker	Race (IOI11_race)	C++17	100 / 100	301 ms	37824 KiB

race

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

#define maxn 200005
#define maxk 1000006
#include<bits/stdc++.h>
using namespace std;
int n, k, sz[maxn], del[maxn], mi[maxk];
vector <int> rollback;
vector <pair<int, int>> a[maxn];
void dfs(int u, int p) {
    sz[u] = 1;
    for (auto [v, w] : a[u]) if (v != p && !del[v]) dfs(v, u), sz[u] += sz[v];
}
int centroid(int u, int p, int cnt) {
    for (auto [v, w] : a[u]) if (v != p && !del[v] && sz[v] * 2 > cnt) return centroid(v, u, cnt);
    return u;
}
int ans = 1e9;
void query(int u, int p, int d, int len, int op) {
    if (len > k) return;
    if (op == 0) ans = min(ans, d + mi[k - len]);
    else {
        mi[len] = min(mi[len], d);
        rollback.push_back(len);
    }
    for (auto [v, w] : a[u]) if (v != p && !del[v])
        query(v, u, d+1, len+w, op);
}
void CentroidDecomposition(int u) {
    dfs(u, -1);
    int cen = centroid(u, -1, sz[u]);
    del[cen] = 1;

    mi[0] = 0;
    for (auto [v, w] : a[cen]) if (!del[v]) {
        query(v, cen, 1, w, 0);
        query(v, cen, 1, w, 1);
    }
    for (int x:rollback) mi[x] = 1e9;
    rollback.clear();

    for (auto [v, w] : a[cen]) if (!del[v])
        CentroidDecomposition(v);
}
int best_path(int N, int K, int H[][2], int L[])
{
  n = N, k = K;
  for (int i=0; i<n-1; i++)
  {
      int u = H[i][0], v = H[i][1], w = L[i];
      a[u].push_back({v, w});
      a[v].push_back({u, w});
  }
  for (int i=1; i<=1e6; i++) mi[i] = 1e9;
  CentroidDecomposition(0);
  if (ans > n) ans = -1;
  return ans;
}

#ifdef yugi
main() {
    int n, k; cin >> n >> k;
    int h[n+1][2], l[n+1];
    for (int i=0; i<n-1; i++) {
        cin >> h[i][0] >> h[i][1] >> l[i];
    }
    cout << best_path(n, k, h, l);
}
#endif // yugi

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