| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 478714 | byungkyu | 경주 (Race) (IOI11_race) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define pii pair<ll,ll>
#define fi first
#define se second
using namespace std;
vector<pii> ch[200005];
vector<ll> st;
set<ll> se;
ll sz[200005],cent[200005],dp[1000005],ret=1e6,l;
ll getsz(ll n,ll pa){
sz[n]=1;
for(auto a : ch[n]){
if(a.fi==pa||cent[a.fi])continue;
sz[n]+=getsz(a.fi,n);
}
return sz[n];
}
ll getcent(ll now,ll pa,ll cap){
ll b,m=cap-sz[now];
for(auto a : ch[now]){
if(a.fi==pa||cent[a.fi])continue;
m=max(m,sz[a.fi]);
b=getcent(a.fi,now,cap);
if(b)return b;
}
if(m*2<=cap)return now;
return 0;
}
ll adjmax(ll now,ll pa){
ll k=0;
for(auto a : ch[now]){
if(a.fi==pa)continue;
if(cent[a.fi])k=max(k,cent[a.fi]);
else k=max(k,adjmax(a.fi,now));
}
return k;
}
void dfs(ll now,ll pa,ll th,ll w,ll dis){
if(w>l)return;
st.push_back(w);
if(l>=w&&dp[l-w]!=-1)ret=min(ret,dp[l-w]+dis);
for(auto a : ch[now]){
if(a.fi==pa)continue;
if(cent[a.fi]<=th)continue;
dfs(a.fi,now,th,w+a.se,dis+1);
}
dp[w]=dis;
}
void solve(){
ll i,j,k,a,b,c,n;
scanf("%lld%lld",&n,&l);
for(i=1;i<n;i++){
scanf("%lld%lld%lld",&a,&b,&c);
a++;b++;
ch[a].push_back({b,c});
ch[b].push_back({a,c});
}
for(i=1;i<=n;i++){
se.insert(i);
}
while(!se.empty()){
a=*se.begin();
k=getsz(a,0);
b=getcent(a,0,k);
cent[b]=adjmax(a,0)+1;
//printf("%lld %lld\n",b,cent[b]);
se.erase(se.find(b));
}
for(i=1;i<=l;i++)dp[i]=-1;
for(i=1;i<=n;i++){
for(auto t : ch[i]){
if(cent[t.fi]<=cent[i])continue;
//printf("new %lld %lld\n",i,t.fi);
dfs(t.fi,i,cent[i],t.se,1);
}
while(st.size()){
dp[st.back()]=-1;
st.pop_back();
}
}
if(ret==1e6)printf("-1");
else printf("%lld\n",ret);
}
int main(){
int T=1;
freopen("grader.in.1","r",stdin);
//scanf("%d",&T);
while(T--){
solve();
}
}