Submission #1143837

#TimeUsernameProblemLanguageResultExecution timeMemory
1143837pedreitorzeldaRace (IOI11_race)C++20
0 / 100
0 ms320 KiB
#include <bits/stdc++.h> using namespace std; vector<bool>vis; vector<map<int,int>>nodes; vector<pair<int,int>>to_add; // lz propagation for subtrees vector<vector<pair<int,int>>>g; int n,k; int cur_ans = -1; void merge(int node1, pair<int,int>b){ int node2 = b.first; int val = b.second; swap(node1,node2); pair<int,int>change = {0,0}; if(nodes[node1].size()>nodes[node2].size()){ swap(nodes[node1],nodes[node2]); swap(to_add[node1],to_add[node2]); to_add[node2].first+=val; to_add[node2].second++; change.first+=val; change.second++; }else{ to_add[node1].first+=val; to_add[node1].second++; } // add current node to to_add[node1] pair<int,int>cur_node_val = make_pair(val-to_add[node1].first,1-to_add[node1].second); // check good answer for current node pair<int,int>cur_node_check = cur_node_val; cur_node_check.first+=change.first; cur_node_check.second+=change.second; cur_node_check.first+=to_add[node1].first; cur_node_check.second+=to_add[node1].second; cur_node_check.first-=to_add[node2].first; cur_node_check.second-=to_add[node2].second; //cout << "SEARCHING " << cur_node_check.first << " " << cur_node_check.second << " " << to_add[node1].first << " " << to_add[node1].second<< endl; if(nodes[node2].find(k-cur_node_check.first)!=nodes[node2].end()){ if(cur_ans==-1)cur_ans = cur_node_check.second+nodes[node2][k-cur_node_check.first]; else cur_ans=min(cur_ans,cur_node_check.second+nodes[node2][k-cur_node_check.first]); } // check good answers for(pair<int,int>it : nodes[node1]){ it.first+=to_add[node1].first; it.second+=to_add[node1].second; it.first-=to_add[node2].first; it.second-=to_add[node2].second; //cout << "SEARCHING " << it.first << " " << it.second << " " << to_add[node1].first << " " << to_add[node1].second<< endl; if(nodes[node2].find(k-it.first)!=nodes[node2].end()){ if(cur_ans==-1)cur_ans = it.second+nodes[node2][k-it.first]; else cur_ans=min(cur_ans,it.second+nodes[node2][k-it.first]); } } // add current node if(nodes[node1].find(cur_node_val.first)==nodes[node1].end())nodes[node1][cur_node_val.first]=cur_node_val.second; else nodes[node1][cur_node_val.first]=min(cur_node_val.second,nodes[node1][cur_node_val.first]); // remake nodes[node2] for(pair<int,int> it : nodes[node1]){ it.first+=to_add[node1].first; it.second+=to_add[node1].second; it.first-=to_add[node2].first; it.second-=to_add[node2].second; // add to current node if(nodes[node2].find(it.first)==nodes[node2].end())nodes[node2][it.first]=it.second; else nodes[node2][it.first]=min(it.second,nodes[node2][it.first]); } } void dfs(int u){ if(vis[u])return; vis[u]=true; for(auto it : g[u]){ if(!vis[it.first]){ dfs(it.first); merge(u,it); //cout << u << ": "; //for(auto it2 : nodes[u]){ // cout << "("<<it2.first << ", " << it2.second << ")" << " "; //}cout << "--- " << to_add[u].first << ", " << to_add[u].second << endl; } } return; } int best_path(int N, int K,int H[][2], int L[]){ nodes.resize(N+2); vis.resize(N+2,0); to_add.resize(N+2,{0,0}); g.resize(N+2); n=N,k=K; cur_ans = -1; for(int i=0;i<N-1;i++){ g[H[i][0]].push_back({H[i][1],L[i]}); g[H[i][1]].push_back({H[i][0],L[i]}); }int root = 0; for(int i=0;i<N;i++){ if(g[root].size()>g[i].size())root=i; }dfs(root);// g[root].size()==1 siempre nodes.clear(); vis.clear(); g.clear(); to_add.clear(); return cur_ans; } /* int main(){ int n,k; cin >> n >> k; int H[n][2]; int L[n]; for(int i=0;i<n-1;i++){ for(int j=0;j<2;j++){ cin >> H[i][j]; } } for(int i=0;i<n-1;i++)cin >> L[i]; cout << best_path(n,k,H,L) << endl; 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...