Submission #100403

#TimeUsernameProblemLanguageResultExecution timeMemory
100403SuperJumboRace (IOI11_race)C++14
9 / 100
3042 ms21260 KiB
#include <bits/stdc++.h> #define NMAX 500001 #define inf (INT_MAX>>2) #define ll long long #define add push_back #define mp make_pair #include "race.h" using namespace std; #define min(a,b) (a > b ? b : a) vector<pair<int,int>> g[NMAX]; int tot, k, ans; int sz[NMAX], cen[NMAX]; int all[NMAX]; void dfs(int node,int par){ sz[node] = 1; for(auto e:g[node]){ int x = e.first; if(x == par || cen[x] )continue; dfs(x,node); sz[node] += sz[x]; } tot = max(tot,sz[node]); } int centroid(int node,int par){ for(auto e:g[node]){ int x = e.first; if(x!=par && sz[x]> tot/2 && !cen[x]){ return centroid(x,node); } } cen[node] = 1; return node; } void dfs2(int node, int par, int cc, int len, unordered_map<int,int> & sub){ if(len == k) ans = min(ans, cc); if(len >= k) return; if(all[k-len]) ans = min(ans,all[k-len]+cc); if(!sub[len]) sub[len] = cc; sub[len] = min(sub[len],cc); for(auto e:g[node]){ int x = e.first; if(!cen[x] && x != par) dfs2(x,node,cc+1,len + e.second,sub); } } void dcmp(int node,int par){ tot = 0; dfs(node,par); int c = centroid(node,par); memset(all,0,sizeof(all)); for(auto e :g[c]){ int x = e.first; if(cen[x])continue; unordered_map<int,int> sub; dfs2(x,c,1,e.second, sub); for(auto u:sub) all[u.first] = all[u.first] == 0 ? u.second : min(all[u.first],u.second); } for(auto e:g[c]){ int x = e.first; if(!cen[x]) dcmp(x,c); } } int best_path(int n,int K,int h[][2] ,int L[]) { k = K; for(int i = 0 ;i<n-1;i++){ int u = h[i][0], v = h[i][1]; g[u].add(mp(v,L[i]));g[v].add(mp(u,L[i])); } memset(cen,0,sizeof(cen)); ans = inf; dcmp(0,-1); ans = ans == inf ? -1: ans; 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...