제출 #580867

#제출 시각아이디문제언어결과실행 시간메모리
580867benson1029경주 (Race) (IOI11_race)C++14
31 / 100
880 ms53544 KiB
#include "race.h" #include<bits/stdc++.h> using namespace std; vector< pair<int,int> > edg[200005]; int k; bool solved[200005]; int compsize[200005]; int mxdeg, centroid; vector< pair<long long, int> > v; set< pair<long long, int> > v2; int ans = 1e9; void findcentroid(int x, int p, int totsize) { int deg = 0; compsize[x] = 1; if(p!=-1) ++deg; for(auto i:edg[x]) { if(!solved[i.first] && i.first!=p) { findcentroid(i.first, x, totsize); compsize[x] += compsize[i.first]; ++deg; } } bool ok = true; for(auto i:edg[x]) { if(!solved[i.first] && i.first!=p) { if(compsize[i.first] > totsize/2) ok = false; } } if(totsize - compsize[x] > totsize/2) ok = false; if(ok) centroid = x; } void solve(int x); void findandsolve(int x) { mxdeg = -1; findcentroid(x, -1, compsize[x]); solve(centroid); } void dfs(int x, int p, long long len, int cnt) { v.push_back({len, cnt}); for(auto i:edg[x]) { if(solved[i.first]) continue; if(i.first != p) { dfs(i.first, x, len+i.second, cnt+1); } } } void solve(int x) { v.clear(); v2.clear(); v2.insert({0, 0}); solved[x] = true; for(auto i:edg[x]) { if(solved[i.first]) continue; v.clear(); dfs(i.first, -1, i.second, 1); sort(v.begin(), v.end()); for(auto i:v) { auto tmp = v2.lower_bound(make_pair(k-i.first, 0)); if(tmp!=v2.end() && (*tmp).first == k-i.first) { ans = min(ans, (*tmp).second + i.second); } } for(auto i:v) { v2.insert(i); } } for(auto i:edg[x]) { if(solved[i.first]) continue; findandsolve(i.first); } } int best_path(int N, int K, int H[][2], int L[]) { k = K; for(int i=0; i<N-1; i++) { edg[H[i][0]].push_back({H[i][1], L[i]}); edg[H[i][1]].push_back({H[i][0], L[i]}); } compsize[0] = N; findandsolve(0); if(ans==1e9) return -1; return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...