#include "race.h"
#pragma GCC optimize("O3")
#include<bits/stdc++.h>
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define in insert
#define er erase
#define fd find
#define fr first
#define sc second
typedef long long ll;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll llinf=(1LL<<61);
const int inf=(1<<30);
const int nmax=1e6+50;
const int mod=1e9+7;
using namespace std;
int x,y,i,n,cent[nmax],sz[nmax],k,ans=1e9,rs[nmax];
vector<pair<int,int> >a[nmax];
vector<int>vc;
void dfs_sz(int u,int p)
{
sz[u]=1;
for(int i=0;i<a[u].size();i++)
{
int v=a[u][i].fr;
if(cent[v] || v==p)continue;
dfs_sz(v,u);
sz[u]+=sz[v];
}
}
int dfs_cent(int u,int p,int siz)
{
for(int i=0;i<a[u].size();i++)
{
int v=a[u][i].fr;
if(cent[v] || v==p)continue;
if(sz[v]>siz/2)return dfs_cent(v,u,siz);
}
return u;
}
void dfs(int x,int p,int d,int lvl,int kp)
{
if(d>k)return;
if(kp)
{
rs[d]=min(rs[d],lvl);
vc.pb(d);
}
else if(rs[k-d]!=1e9)ans=min(ans,lvl+rs[k-d]);
for(int i=0;i<a[x].size();i++)
{
int y=a[x][i].fr,v=a[x][i].sc;
if(y==p || cent[y])continue;
if(!lvl)
{
dfs(y,x,d+v,lvl+1,0);
dfs(y,x,d+v,lvl+1,1);
}
else dfs(y,x,d+v,lvl+1,kp);
}
}
void decompose(int root,int p=-1)
{
dfs_sz(root,p);
int c=dfs_cent(root,p,sz[root]);
cent[c]=1;
vc.clear();
dfs(c,p,0,0,1);
for(int i=0;i<vc.size();i++)rs[vc[i]]=1e9;
rs[0]=0;
rs[0]=0;
for(int i=0;i<a[c].size();i++)
{
int v=a[c][i].fr;
if(cent[v])continue;
decompose(v,c);
}
}
int best_path(int n,int k,int h[][2],int l[])
{
for(i=0;i<n-1;i++)
{
x=h[i][0]+1,y=h[i][1]+1;
int lt=l[i];
a[x].pb(pair<int,int>(y,lt));
a[y].pb(pair<int,int>(x,lt));
}
for(i=1;i<=k;i++)rs[i]=1e9;
decompose(1);
if(ans==1e9)return -1;
else return ans;
}
/*int main()
{
//freopen("sol.in","r",stdin);
//freopen("sol.out","w",stdout);
ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
cin>>n>>k;
for(i=1;i<n;i++)
{
int l;
cin>>x>>y>>l;
x++,y++;
a[x].pb({y,l});
a[y].pb({x,l});
}
for(i=1;i<=k;i++)rs[i]=1e9;
decompose(1);
if(ans==1e9)cout<<-1<<endl;
else cout<<ans<<endl;
return 0;
}
/*
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
*/
Compilation message
race.cpp:114:1: warning: "/*" within comment [-Wcomment]
/*
race.cpp: In function 'void dfs_sz(int, int)':
race.cpp:24:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<a[u].size();i++)
~^~~~~~~~~~~~
race.cpp: In function 'int dfs_cent(int, int, int)':
race.cpp:34:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<a[u].size();i++)
~^~~~~~~~~~~~
race.cpp: In function 'void dfs(int, int, int, int, int)':
race.cpp:51:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<a[x].size();i++)
~^~~~~~~~~~~~
race.cpp: In function 'void decompose(int, int)':
race.cpp:70:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<vc.size();i++)rs[vc[i]]=1e9;
~^~~~~~~~~~
race.cpp:73:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<a[c].size();i++)
~^~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
25 ms |
23928 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
25 ms |
23928 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
25 ms |
23928 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
25 ms |
23928 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
