제출 #555566

#제출 시각아이디문제언어결과실행 시간메모리
555566xdfactor2034경주 (Race) (IOI11_race)C++17
0 / 100
16 ms23820 KiB
#include<bits/extc++.h> using namespace std; using namespace __gnu_pbds; #define int long long const int mxN = 1e6+5; using pii = pair<int,int>; vector<pii> tr[mxN]; int sbsz[mxN], seen[mxN], N, K, res = LLONG_MAX, within; int gsb(int x, int p=-1) { sbsz[x] = 1ll; #define nn it.second for(auto it : tr[x]) if(!seen[nn] && nn != p) sbsz[x] += gsb(nn, x); return sbsz[x]; } int gc(int x, int p=-1) { for(auto it : tr[x]) if(!seen[nn] && nn != p && sbsz[nn]*2ll>within) return gc(nn,x); seen[x]=1; return x; } gp_hash_table<int,int> rol, loc; void pdfs(int x, int p, int dist, int len) { assert(!seen[x]); if(dist > K) return; if(loc.find(dist) == loc.end()) loc[dist] = len; else loc[dist] = min(loc[dist], len); for(auto it : tr[x]) if(!seen[nn] && nn != p) { pdfs(nn, x, dist + it.first, len+1ll); } } void de(int x){ within = gsb(x,-1); int cen = gc(x,-1); rol.clear(); loc.clear(); for(auto it : tr[cen]) if(!seen[nn]) { loc.clear(); pdfs(nn, cen, it.first, 1ll); for(auto en : loc) { if(K-en.first < 0) continue; if(rol.find(K-en.first) != rol.end()) res = min(res, en.second+rol[K-en.first]); } for(auto en : loc) { if(en.first < 0 || en.first > K) continue; if(rol.find(en.first) == rol.end()) rol[en.first] = en.second; else rol[en.first] = min(rol[en.first], en.second); } } for(auto it : tr[cen]) if(!seen[nn]) { de(nn); } } signed best_path(signed n, signed k, signed h[][2], signed l[]) { N = n, K = k; for(int i = 0; i < N-1; i++) { int a = h[i][0], b = h[i][1], w = l[i]; tr[a].push_back({w,b}); tr[b].push_back({w,a}); } de(0); if(res == LLONG_MAX) return -1; else return res; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...