제출 #793524

#제출 시각아이디문제언어결과실행 시간메모리
793524limabeans경주 (Race) (IOI11_race)C++17
0 / 100
3 ms4948 KiB
#include <algorithm> #include <iostream> #include <vector> #include <cassert> #include <map> using namespace std; using ll = long long; const int maxn=2e5+10; vector<pair<ll,int>> g[maxn]; bool alive[maxn]; int siz[maxn]; int dfs(int at, int p) { siz[at] = 1; for (auto ed: g[at]) { int to = ed.second; if (to==p) continue; if (!alive[to]) continue; siz[at] += dfs(to, at); } return siz[at]; } void dfs2(int at, int p, int &centroid, int cnt) { int hi = 0; for (auto ed: g[at]) { int to = ed.second; if (to==p) continue; if (!alive[to]) continue; dfs2(to,at,centroid,cnt); hi = max(hi, siz[to]); } hi = max(hi, cnt-siz[at]); //cout<<at<<": hi: "<<hi<<endl; if (hi+hi<=cnt) centroid=at; } int ans; // dp[sum] = min_length map<ll,int> solve(int at, ll k, int n) { dfs(at,at); int cnt = siz[at]; int centroid = -1; dfs2(at,at,centroid,cnt); assert(~centroid); //cout<<at<<":--> "<<centroid<<endl; at = centroid; alive[at] = false; map<ll,int> dp; for (auto ed: g[at]) { int to = ed.second; if (alive[to]) { auto rec = solve(to, k, n); for (auto p: rec) { ll wei = ed.first + p.first; int len = p.second; if (dp.count(k-wei)) { ans = min(ans, len+1+dp[k-wei]); } } for (auto p: rec) { ll wei = ed.first + p.first; int len = p.second; if (!dp.count(wei)) dp[wei]=n; dp[wei] = min(dp[wei], len+1); } } } dp[0] = 0; // cout<<"at: "<<at<<endl; // for (auto p: dp) cout<<p.first<<": "<<p.second<<endl; return dp; } int best_path(int n, int k, int H[][2], int L[]) { for (int i=0; i<n-1; i++) { int u=H[i][0]; int v=H[i][1]; int w=L[i]; g[v].push_back({w,u}); g[u].push_back({w,v}); } for (int i=0; i<n; i++) { alive[i]=true; } ans = n; solve(0,k,n); if (ans == n) ans = -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...