| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1105066 | whoknow | Race (IOI11_race) | C++17 | 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 <bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define MAXN 200005
#define MAXK 1000005
#define ii pair<int,int>
#define bit(i,j) ((i>>j)&1)
#define sz(i) (int)i.size()
#define endl '\n'
using namespace std;
const int INF = 1e9 + 7;
int n, K;
vector<ii>g[MAXN];
namespace sub1
{
int res = INF;
int sz[MAXN], h[MAXN];
ll s[MAXN];
bool del[MAXN];
vector<int>dp(MAXK);
vector<bool>dd(MAXK);
int cnt(int u, int p)
{
sz[u] = 1;
for(ii i : g[u])
{
int v = i.F;
if(v == p || del[v])
continue;
sz[u] += cnt(v, u);
}
return sz[u];
}
int centroid(int u, int p, int cnt)
{
for(ii i : g[u])
{
if(i.F == p || del[i.F])
continue;
if(sz[i.F] > cnt / 2)
return centroid(i.F, u, cnt);
}
return u;
}
void dfs(int u, int p)
{
h[u] = h[p] + 1;
if(s[u]>K)
return s[u]=0,void();
if(K >= s[u])
if(dp[K - s[u]] && dd[K - s[u]])
res = min(res, dp[K - s[u]] + h[u]);
for(ii i : g[u])
{
int v = i.F, w = i.S;
if(v == p || del[v])
continue;
s[v] = s[u] + w;
dfs(v, u);
}
}
void clr(int u, int p)
{
if(dd[s[u]])
dp[s[u]] = min(dp[s[u]], h[u]);
else
dp[s[u]] = h[u];
dd[s[u]] = 1;
s[u] = 0, h[u] = 0;
for(ii i : g[u])
{
int v = i.F;
if(v == p || del[v])
continue;
clr(v, u);
}
}
void build(int u, int p)
{
int mid = centroid(u, 0, cnt(u, 0));
dd[0] = 1;
for(ii i : g[mid])
{
int v = i.F, w = i.S;
if(del[v])
continue;
s[v] = s[mid] + w;
dfs(v, mid);
clr(v, mid);
}
vector<int>(MAXK).swap(dp);
vector<bool>(MAXK).swap(dd);
del[mid] = 1;
for(ii i : g[mid])
{
int v = i.F;
if(del[v])
continue;
build(v, mid);
}
}
void solve()
{
build(1, 0);
cout << res;
}
}
main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> K;
for(int i = 1; i < n; i++)
{
int x, y, z;
cin >> x >> y >> z;
x++, y++;
g[x].push_back({y, z});
g[y].push_back({x, z});
}
sub1::solve();
}
/**
11 12
0 1 3
0 2 4
2 3 5
3 4 4
4 5 6
0 6 3
6 7 2
6 8 5
8 9 6
8 10 7
**/