| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 254450 | StevenH | Race (IOI11_race) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// #include "race.h"
#include <bits/stdc++.h>
using namespace std;
const int maxk = 1e6 + 5;
const int maxn = 2e5 + 5;
const int inf = 1e9;
int dis[maxn], depth[maxn];
int n, k;
int vis[maxn];
int ans;
vector<vector<pair<int, int> > > edge(maxn);
int cur, tag[maxk], pt[maxk];
inline void reset(int dist)
{
if (tag[dist] != cur)
{
tag[dist] = cur;
pt[dist] = dist ? inf : 0;
}
return;
}
int dfn[maxn], last[maxn], rnk[maxn], cnt;
void init(int u, int f)
{
dfn[u] = ++cnt;
rnk[cnt] = u;
for (int i = 0; i < edge[u].size(); i++)
{
int v = edge[u][i].first;
int dist = edge[u][i].second;
if (f == v || vis[v])
continue;
dis[v] = dis[u] + dist;
depth[v] = depth[u] + 1;
init(v, u);
}
last[u] = cnt;
return;
}
int size[maxn], son[maxn];
void find_rt(int u, int f, int &root)
{
size[u] = 1;
for (int i = 0; i < edge[u].size(); i++)
{
int v = edge[u][i].first;
if (f == v || vis[v])
continue;
find_rt(v, u, root);
son[u] = max(son[u], size[v]);
size[u] += size[v];
}
if (son[u] <= son[root])
root = u;
return;
}
void dfs1(int u)
{
vis[u] = 1;
cur++;
// memset(pt, 0x3f, sizeof(pt));
pt[0] = 0;
for (int i = 0; i < edge[u].size(); i++)
{
int v = edge[u][i].first;
if (vis[v])
continue;
for (int j = dfn[v]; j <= last[v]; j++)
{
int dist = dis[rnk[j]];
int dep = depth[rnk[j]];
if (dist > k)
continue;
reset(k - dist);
ans = min(ans, dep + pt[k - dist]);
}
for (int j = dfn[v]; j <= last[v]; j++)
{
int dist = dis[rnk[j]];
int dep = depth[rnk[j]];
if (dist > k)
continue;
reset(dist);
pt[dist] = min(pt[dist], dep);
}
}
for (int i = 0; i < edge[u].size(); i++)
{
int v = edge[u][i].first;
if (vis[v])
continue;
int rt = v;
son[rt] = n;
find_rt(v, -1, rt);
depth[rt] = 0;
dis[rt] = 0;
// memset(depth, 0, sizeof(depth));
// memset(dis, 0, sizeof(dis));
// memset(dfn, 0, sizeof(dfn));
// memset(rnk, 0, sizeof(rnk));
cnt = 0;
init(rt, -1);
dfs1(rt);
}
return;
}
int best_path(int N, int K, int H[][2], int L[])
{
for (int i = 0; i < N - 1; i++)
{
edge[H[i][0]].push_back(make_pair(H[i][1], L[i]));
edge[H[i][1]].push_back(make_pair(H[i][0], L[i]));
}
k = K;
n = N;
ans = N + 1;
int rt = 0;
son[rt] = n;
find_rt(0, -1, rt);
depth[rt] = 0;
dis[rt] = 0;
init(rt, -1);
dfs1(rt);
if (ans == N + 1)
return -1;
return ans;
}
#define MAX_N 500000
static int N, K;
static int H[MAX_N][2];
static int L[MAX_N];
static int solution;
void read_input()
{
int i;
scanf("%d %d", &N, &K);
for (i = 0; i < N - 1; i++)
scanf("%d %d %d", &H[i][0], &H[i][1], &L[i]);
}
int main()
{
int ans;
read_input();
ans = best_path(N, K, H, L);
printf("%d\n", ans);
return 0;
}