Submission #221313

#TimeUsernameProblemLanguageResultExecution timeMemory
221313a_playerRace (IOI11_race)C++14
0 / 100
49 ms8960 KiB
#include "race.h" #include <bits/stdc++.h> #define f first #define s second using namespace std; const int nax=2e5+5; const int vax=1e6+5; typedef long long ll; vector<pair<int,int> > grafo[nax]; int ans=INT_MAX; int N,K; int ss,cc; int m[vax]; set<int> vis; void incl(int n, int a, int d, int v){ if(K<v)return; if(a!=-1){ if(m[K-v]!=-1)ans=min(ans,m[K-v]+d); if(m[v]==-1)m[v]=d; else m[v]=min(m[v],d); }else{ fill(m,m+vax,-1); } for(auto x:grafo[n]){ if(!vis.count(x.f)&&x.f!=a){ incl(x.f,n,d+1,v+x.s); } } } int findc(int n, int a, int& c, int num){ int s=0; for(auto x:grafo[n]){ if(x.f!=a&&!vis.count(x.f)){ s+=findc(x.f,n,c,num); } } if(abs(s-num/2)<=1)c=n; return s+1; } int findsize(int n, int a){ int s=0; for(auto x:grafo[n]){ if(!vis.count(x.f)&&x.f!=a){ s+=findsize(x.f,n); } } return s+1; } void centroid(int n){ incl(n,-1,0,0); vis.insert(n); for(auto x:grafo[n]){ if(vis.count(x.f))continue; ss=findsize(x.f,-1); findc(x.f,-1,cc,ss); centroid(cc); } } int best_path(int N, int K, int H[][2], int L[]){ ::N=N,::K=K; for(int i=0;i<N-1;i++){ grafo[H[i][0]].push_back({H[i][1],L[i]}); grafo[H[i][1]].push_back({H[i][0],L[i]}); } ss=findsize(0,-1); findc(0,-1,cc,ss); centroid(cc); if(ans==INT_MAX)return -1; return ans-1; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...