Submission #1093325

#TimeUsernameProblemLanguageResultExecution timeMemory
1093325AvianshRace (IOI11_race)C++17
0 / 100
1 ms348 KiB
#include <bits/stdc++.h> #include "race.h" using namespace std; int subSize(int st, vector<pair<int,int>>(&g)[], int sz[], int par, bool rem[]){ sz[st]=1; for(pair<int,int> p : g[st]){ int c = p.first; if(rem[c]||c==par) continue; sz[st]+=subSize(c,g,sz,st,rem); } return sz[st]; } int findCentroid(int node, vector<pair<int,int>>(&g)[], int siz, bool rem[], int par, int sizes[]){ for(pair<int,int> p : g[node]){ int c = p.first; if(c==par||rem[c]) continue; if(sizes[c]*2>siz){ return findCentroid(c,g,siz,rem,node,sizes); } } return node; } void findLens(int st, vector<pair<int,int>>(&g)[], bool rem[], int par, map<int,int>(&mp), int dep, int len){ for(pair<int,int> p : g[st]){ int c = p.first; int d = p.second; if(c==par||rem[c]) continue; if(mp[dep+d]==0){ mp[dep+d]=len+1; } else{ mp[dep+d]=min(mp[dep+d],len+1); } findLens(c,g,rem,st,mp,dep+d,len+1); } } int buildDecomp(int node, vector<pair<int,int>>(&g)[], bool rem[], int sz[], int k){ int centroid = findCentroid(node,g,subSize(node,g,sz,-1,rem),rem,-1,sz); int ans = INT_MAX; map<int,int>mp; rem[centroid]=1; for(pair<int,int> p : g[centroid]){ int c = p.first; if(rem[c]) continue; map<int,int>temp; temp[p.second]=1; findLens(c,g,rem,-1,temp,p.second,0); for(pair<int,int>pa : temp){ if(mp[k-pa.first]){ ans=min(ans,mp[k-pa.first]+pa.second); } } for(pair<int,int>pa:temp){ if(mp[pa.first]){ mp[pa.first]=min(mp[pa.first],pa.second); } else{ mp[pa.first]=pa.second; } } } for(pair<int,int>p:g[centroid]){ int c = p.first; if(rem[c])continue; ans=min(ans,buildDecomp(c,g,rem,sz,k)); } return ans; } int best_path(int n, int k, int e[][2], int w[]) { vector<pair<int,int>>g[n]; for(int i = 0;i<n-1;i++){ g[e[i][0]].push_back({e[i][1],w[i]}); g[e[i][1]].push_back({e[i][0],w[i]}); } bool rem[n]; int sz[n]; fill(rem,rem+n,0); int ans = buildDecomp(0,g,rem,sz,k); if(ans==INT_MAX){ return -1; } else{ 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...