Submission #1249435

#TimeUsernameProblemLanguageResultExecution timeMemory
1249435Joseph0121Race (IOI11_race)C++20
100 / 100
313 ms63608 KiB
#include <bits/stdc++.h> using namespace std; const int maxn = 2e5+5; vector<pair<int,int>> e[maxn]; int sz[maxn], heavy[maxn], par[maxn], heavy_par[maxn]; map<int,int> mp; int ans = 1e9; void dfs1(int node, int parent){ int heavy_child = -1, sz_child = -1; for(auto i: e[node]){ if(i.first == parent) continue; par[i.first] = node; dfs1(i.first,node); if(sz[i.first] > sz_child){ heavy_child = i.first; sz_child = sz[i.first]; } sz[node]+=sz[i.first]; } sz[node]+=1; heavy[node] = heavy_child; heavy_par[heavy_child] = node; } void dfs3(int node, int parent, int dist_now, int depth, vector<array<int,2>> &node_dist, int K){ node_dist.push_back({dist_now, depth}); if(dist_now > K) return; for(auto i: e[node]){ if(i.first == parent) continue; dfs3(i.first, node, dist_now+i.second, depth+1, node_dist, K); } } array<int,2> dfs2(int node, int parent, int K){ //go down the heavy child first // cout<<node<<" "<<parent<<endl; if(heavy[node] == -1) return {0,0}; // cout<<node<<" "<<parent<<endl; //first return = total weight added, second return = total edges added array<int,2> tmp = dfs2(heavy[node],node,K); int add_weight = tmp[0], add_edge = tmp[1]; add_edge++; for(auto i: e[node]){ if(i.first == heavy[node]){ add_weight+=i.second; break; } } mp[-add_weight] = -add_edge; // for(auto j: mp) cout<<j.first<<" "; // cout<<endl; // cout<<"node: "<<node<<" add_weight: "<<add_weight<<" add_edge: "<<add_edge<<endl; // if(node == 2){ // cout<<"add_weight: "<<add_weight<<endl; // cout<<mp.begin()->first<<endl; // } if(mp.count(K-add_weight) != 0){ ans = min(ans,mp[K-add_weight]+add_edge); // cout<<"node: "<<node<<endl; } //what is the total sum you're adding vector<array<int,2>> node_dist; for(auto i: e[node]){ if(i.first!=parent && i.first!=heavy[node]){ dfs3(i.first, node, i.second, 1, node_dist, K); //now I have all the distances // for(auto j: node_dist) cout<<j[0]<<" "<<j[1]<<endl; for(auto j: node_dist){ //j[0] = distance, j[1] = minimum edges to cover if(mp.count(K-add_weight-j[0]) != 0){ // cout<<"node: "<<node<<endl; ans = min(ans,mp[K-add_weight-j[0]]+j[1]+add_edge); } } //add everything in for(auto j: node_dist){ if(mp.count(j[0]-add_weight) != 0){ mp[j[0]-add_weight] = min(mp[j[0]-add_weight], j[1]-add_edge); } else mp[j[0]-add_weight] = j[1]-add_edge; } node_dist.clear(); } } return {add_weight, add_edge}; } int best_path(int N, int K, int H[][2], int L[]){ for(int i = 0;i<N;i++){ par[i] = -1; heavy_par[i] = -1; } for(int i = 0;i<N-1;i++){ e[H[i][0]].push_back(make_pair(H[i][1],L[i])); e[H[i][1]].push_back(make_pair(H[i][0],L[i])); } dfs1(0,0); //all the heavy children // for(int i = 0;i<N;i++){ // cout<<heavy[i]<<" "<<sz[i]<<endl; // } // cout<<endl; for(int i = 0;i<N;i++){ if(heavy_par[i] == -1){ //it's top of a chain mp[0] = 0; dfs2(i,par[i],K); mp.clear(); } } if(ans == 1e9) 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...