제출 #126439

#제출 시각아이디문제언어결과실행 시간메모리
126439jaaguptamme경주 (Race) (IOI11_race)C++14
9 / 100
134 ms28200 KiB
#include <bits/stdc++.h> #define ll long long #define pii pair<ll,ll> #include "race.h" using namespace std; const ll N=200005; vector<pii>g[N]; map<ll,ll>*mp[N]; ll dist[N],sz[N],dep[N]; ll res=INT_MAX; ll k; void dfs(ll u,ll prev){ sz[u]=1; ll mxsz=-1,mxn=-1; for(auto el:g[u]){ ll v=el.first; ll c=el.second; if(v==prev)continue; dist[v]=dist[u]+c; dep[v]=dep[u]+1; dfs(v,u); sz[u]+=sz[v]; if(sz[v]>mxsz){ mxsz=sz[v]; mxn=v; } } if(mxsz!=-1)mp[u]=mp[mxn]; else mp[u]=new map<ll,ll>(); if((*mp[u]).count(dist[u]))(*mp[u])[dist[u]]=min((*mp[u])[dist[u]],dep[u]); else (*mp[u])[dist[u]]=dep[u]; if((*mp[u]).count(k+dist[u])){ ll node=(*mp[u])[k+dist[u]]; //cout<<"CHANG"<<k-dist[u]<<' '<<node<<' '<<dep[u]<<' '<<u<<'\n'; res=min(res,abs(node-dep[u])); } for(auto E:g[u]){ ll v=E.first; if(v==prev ||v==mxn)continue; for(auto el:(*mp[v])){ ll nx=el.first; ll de=el.second; if((*mp[u]).count(k-nx)){ ll node=(*mp[u])[k-nx]; res=min(res,abs(de-dep[u])+abs(dep[u]-node)); // cout<<"CHANGE"<<nx<<' '<<k<<' '<<de<<' '<<res<<'\n'; } } for(auto el:(*mp[v])){ ll nx=el.first; ll de=el.second; if((*mp[u]).count(nx)){ (*mp[u])[nx]=min((*mp[u])[nx],de); }else (*mp[u])[nx]=de; } } /* cout<<"NODE"; cout<<u<<' '<<prev<<' '<<dist[u]<<' '<<dep[u]<<'\n'; for(auto el:(*mp[u]))cout<<el.first<<' '<<el.second<<'\n'; */ } int best_path(int N, int K, int H[][2], int L[]) { k=K; for(int i=0;i<N-1;i++){ ll u,v,c;u=H[i][0]; v=H[i][1]; c=L[i]; g[u].push_back({v,c}); g[v].push_back({u,c}); } dep[1]=0; dfs(1,N); int ans=res; if(ans<=N)return ans; else return -1; } /* int main(){ int n=4; int k=7; int h[][2]={{0,1},{1,2},{1,3}}; int l[]={1,2,4}; std::cout<<best_path(n,k,h,l)<<'\n'; } */ /* int main(){ int n=11; int k=12; int h[][2]={{0,1},{0,2},{2,3},{3,4},{4,5},{0,6},{6,7},{6,8},{8,9},{8,10}}; int l[]={3,4,5,4,6,3,2,5,6,7}; cout<<best_path(n,k,h,l)<<'\n'; } */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...