| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 468053 | starplat | 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 <bits/stdc++.h>
#define ll long long
#define pb push_back
#define f first
#define s second
#define pll pair<ll,ll>
using namespace std;
ll n,k,u,v,w,freq[10000005],ans;
ll marked[200005],ctree[200005],tree[200005];
vector<pll> g[200005];
void subtree(int x,int p)//subtree size
{
if (marked[x]) return;
tree[x]=1;
for (pll i:g[x]){
if (p!=i.f&&!marked[i.f]){
subtree(i.f,x);
tree[x]+=tree[i.f];
}
}
}
int find(int x,int ct,int p)
{
for (pll i:g[x]){
if (i.f!=p){
if (!marked[i.f] && tree[i.f]>ct/2) return find(i.f,ct,x);
}
}
return x;
}
void dfs(int x,int p,ll dist,ll lvl)
{
if (dist>k) return;
ans=min(ans,lvl+freq[k-dist]);
//cout<<"dfs "<<x<<" "<<p<<" "<<dist<<" "<<lvl<<" "<<freq[k-dist]<<" "<<ans<<"\n";
if (dist==k) ans=min(ans,lvl);
for (pll i:g[x]){
if (i.f!=p &&!marked[i.f]){
dfs(i.f,x,dist+i.s,lvl+1);
}
}
}
void dfs1(int x,int p,ll dist,ll lvl)
{
if (dist>k) return;
freq[dist]=min(lvl,freq[dist]);
//cout<<"dfs1"<<" "<<x<<" "<<p<<" "<<dist<<" "<<lvl<<" "<<freq[dist]<<"\n";
if (dist==k) ans=min(ans,lvl);
for (pll i:g[x]){
if (!marked[i.f]&&i.f!=p){
dfs1(i.f,x,dist+i.s,lvl+1);
}
}
}
void subtreeclear(int x,int p,ll dist)
{
if (dist>k) return;
freq[dist]=INT_MAX;
for (pll i:g[x]){
if (!marked[i.f]&&i.f!=p){
subtreeclear(i.f,x,dist+i.s);
}
}
}
int build(int x)
{
subtree(x,-1);
int node=find(x,tree[x],-1);
//cout<<node<<"\n";
marked[node]=1;
freq[0]=INT_MAX;
for (pll i:g[node]){
if (!marked[i.f]){
dfs(i.f,node,i.s,1);
dfs1(i.f,node,i.s,1);
}
}
subtreeclear(node,-1,0);
for (pll i:g[node]){
if (!marked[i.f]){
ctree[build(i.f)]=node;
}
}
return node;
}
int main()
{
cin>>n>>k;
for (int i=1;i<n;i++){
cin>>u>>v>>w;
g[u].pb({v,w});
g[v].pb({u,w});
}
ans=INT_MAX;
for (int i=0;i<=1e7;i++) freq[i]=INT_MAX;
int root=build(0);
if (ans==INT_MAX) cout<<-1<<endl;
else cout<<ans<<endl;
return 0;
}
/*
properties
1.a vertex belongs to the component of all its ancestors
2.the path from a to b can be decomposed into the path fom a to lca(a,b) and the path from lca(a,b) ,
where lca(a,b) is the lowest common ancestor of a and b in the centroid decomposition
3.the height of the centroid tree is O(log2(n))
*/
/*
11 5
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
1
*/