제출 #218021

#제출 시각아이디문제언어결과실행 시간메모리
218021Andrei_Cotor경주 (Race) (IOI11_race)C++11
43 / 100
317 ms65912 KiB
#include<race.h> #include<vector> #include<set> using namespace std; int nrPaths; set<pair<int,int> > S[200005]; vector<pair<int,int> > A[200005]; int HPath[200005],Dist[200005],Lev[200005]; int dfs(int nod, int p, int L) { int rez=1000000000; for(auto other:A[nod]) { if(other.first==p) continue; Dist[other.first]=Dist[nod]+other.second; Lev[other.first]=Lev[nod]+1; rez=min(rez,dfs(other.first,nod,L)); if(S[HPath[other.first]].size()>S[HPath[nod]].size()) HPath[nod]=HPath[other.first]; } if(HPath[nod]==0) HPath[nod]=++nrPaths; int path=HPath[nod]; for(auto other:A[nod]) { if(other.first==p || path==HPath[other.first]) continue; for(auto el:S[HPath[other.first]]) { int dist=L-(el.first-Dist[nod])+Dist[nod]; if(dist>Dist[nod]) { set<pair<int,int> >::iterator it=S[path].lower_bound({dist,0}); if(it!=S[path].end() && (*it).first==dist) rez=min(rez,(*it).second+el.second-2*Lev[nod]); } set<pair<int,int> >::iterator it=S[path].lower_bound({el.first,0}); if(it!=S[path].end() && (*it).first==el.first) { if(el.second<(*it).second) { S[path].erase(it); S[path].insert(el); } } else S[path].insert(el); } } S[path].insert({Dist[nod],Lev[nod]}); set<pair<int,int> >::iterator it=S[path].lower_bound({Dist[nod]+L,0}); if(it!=S[path].end() && (*it).first==Dist[nod]+L) rez=min(rez,(*it).second-Lev[nod]); return rez; } int best_path(int n, int k, int E[][2], int L[]) { for(int i=0; i<=n-2; i++) { A[E[i][0]].push_back({E[i][1],L[i]}); A[E[i][1]].push_back({E[i][0],L[i]}); } int rez=dfs(0,-1,k); if(rez==1000000000) rez=-1; return rez; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...