Submission #764256

#TimeUsernameProblemLanguageResultExecution timeMemory
764256Ryuga_Race (IOI11_race)C++14
0 / 100
3 ms4948 KiB
#include<bits/stdc++.h> using namespace std; const int N = 2e5 + 10; #define F first #define S second typedef long long ll; vector<pair<int,int>>g[N]; int sub[N] , process[N]; int n , k ; map<ll,int>mp; int dfs(int u , int p) { sub[u] = 1; for(auto v : g[u]){ if(v.F != p && !process[v.F]){ sub[u] += dfs(v.F,u); } } return sub[u]; } int centroid(int u , int p , int req) { for(auto v : g[u]){ if(v.F != p && !process[v.F] && sub[v.F] >= req){ return centroid(v.F,u,req); } } return u; } int ans = INT_MAX; void f(int u ,int p , int keep , ll depth , int level) { if(depth > k) return; if(!keep){ ll x = k-depth; if(mp.find(x) != mp.end()){ ans = min(ans,mp[x] + level); } } else{ if(mp.find(depth) != mp.end()){ mp[depth] = min(mp[depth],level); } else mp[depth] = level; } for(auto v : g[u]){ if(v.F != p && !process[v.F]){ f(v.F,u,keep,depth+v.S,level+1); } } } void decompose(int u) { ll x = dfs(u,-1); ll cen = centroid(u,0,x/2); process[cen] = 1; mp[0] = 0; for(auto v : g[cen]){ if(!process[v.F]){ f(v.F,cen,0,v.S,1); f(v.F,cen,1,v.S,1); } } mp.clear(); for(auto v : g[cen]){ if(!process[v.F]) decompose(v.F); } } int best_path(int _N, int _K, int H[][2], int L[]) { for(int i = 0 ; i < _N - 1 ; i ++){ int x = H[i][0] , y = H[i][1] , w = L[i]; g[x].push_back({y,w}); g[y].push_back({x,w}); } decompose(0); if(ans == INT_MAX) 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...