Submission #1249433

#TimeUsernameProblemLanguageResultExecution timeMemory
1249433Joseph0121Race (IOI11_race)C++20
Compilation error
0 ms0 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; } signed main() { int nn, kk; cin>>nn>>kk; int hh[105][2], ll[106]; for(int i = 0;i<nn;i++) cin>>hh[i][0]>>hh[i][1]>>ll[i]; cout<<best_path(nn,kk,hh,ll); return 0; }

Compilation message (stderr)

/usr/bin/ld: /tmp/ccQnFAEk.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cc6rGulP.o:race.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status