Submission #777426

#TimeUsernameProblemLanguageResultExecution timeMemory
777426a_aguiloRace (IOI11_race)C++14
21 / 100
3077 ms14672 KiB
#include "race.h" #include<bits/stdc++.h> using namespace std; int n, k; const int maxN = 200000; vector<pair<int, int>> AdjList[maxN]; vector<int> exists; int padre[maxN]; int subTreeSize[maxN]; unordered_map<int, int> M; void print(vector<pair<int, int>>& V){ for(pair<int, int>& pii: V){ cout << pii.first << " "; } cout << endl; } void preProcess(int node){ subTreeSize[node] = 1; for(pair<int, int>& next: AdjList[node]){ //cout << node << " -> " << next.first << endl; if(next.first != padre[node] && exists[next.first]){ padre[next.first] = node; preProcess(next.first); subTreeSize[node] += subTreeSize[next.first]; } } //cout << node << " " << subTreeSize[node] << endl; } int find_Centroid(int node, int sze){ for(pair<int, int>& next: AdjList[node]){ if(next.first == padre[node] || !exists[next.first]) continue; if(subTreeSize[next.first] > (sze/2)) return find_Centroid(next.first, sze); } return node; } void findDistances(int node, int currDist, int numEdges, vector<pair<int, int>>& V){ if(currDist > k) return; V.push_back({currDist, numEdges}); for(pair<int, int>& next: AdjList[node]){ if(exists[next.first] && next.first != padre[node]){ padre[next.first] = node; findDistances(next.first, currDist+next.second, numEdges+1, V); } } } int solveSubTree(int node){ padre[node] = node; preProcess(node); int sze = subTreeSize[node]; node = find_Centroid(node, sze); //cout << node << endl; padre[node] = node; M.clear(); int ans = 1e9; for(pair<int, int>& next: AdjList[node]){ if(next.first == padre[node]) continue; if(!exists[next.first]) continue; padre[next.first] = node; vector<pair<int, int>> prov; findDistances(next.first, next.second, 1, prov); for(pair<int, int>& val: prov){ int d = val.first; int edges = val.second; if(M.find(k-d) != M.end())ans = min(ans, M[k - d] + edges); } for(pair<int, int>& val: prov){ int d = val.first; int edges = val.second; if(M.find(d) == M.end()) M[d] = edges; else M[d] = min(M[d], edges); } /* cout << node << " -> " << next.first << endl; for(int i = 1; i <= k; ++i) cout << lengths[i] << " "; cout << endl;*/ } if(M.find(k) != M.end())ans = min(ans, M[k]); exists[node] = 0; for(pair<int, int>& next: AdjList[node]){ if(exists[next.first]) ans = min(ans, solveSubTree(next.first)); } return ans; } int best_path(int N, int K, int H[][2], int L[]) { n = N; k = K; exists = vector<int>(N, 1); M.reserve(262144); int a, b, c; for(int i = 0; i < N-1; ++i){ a = H[i][0]; b = H[i][1]; c = L[i]; AdjList[a].push_back({b, c}); AdjList[b].push_back({a, c}); } /* for(int i = 0; i < N-1; ++i){ cout << i << '\t'; print(AdjList[i]); }*/ int res = solveSubTree(0); if(res == 1e9) return -1; return res; } /* int main(){ int N, K; cin >> N >> K; int H[N-1][2]; int L[N-1]; for(int i = 0; i < N-1; ++i) cin >> H[i][0] >> H[i][1] >> L[i]; cout << best_path(N, K, H, L); return 0; }*/
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...