Submission #1261004

#TimeUsernameProblemLanguageResultExecution timeMemory
1261004hickwhitherRace (IOI11_race)C++20
Compilation error
0 ms0 KiB
#define mocua(inp, out) if(fopen(inp,"r")){freopen(inp,"r",stdin);freopen(out,"w",stdout);} #include <iostream> #include <cstdint> #include <climits> #include <vector> #include <cstring> using namespace std; int numNode, desiredLength; vector<int> e[int(2e5+3)]; vector<pair<int,int>> elen[int(2e5+3)]; bool removed[int(2e5+3)]; int sz[int(2e5+3)]; int depth[int(2e5+3)]; void calsize(int u, int p=-1){ sz[u] = 1; for(int &v : e[u]) if(!removed[v] && v!=p){ depth[v] = depth[u]+1; calsize(v, u); sz[u] += sz[v]; } } int find_centroid(int targetsize, int u, int p=-1){ for(int &v : e[u]) if(!removed[v] && v!=p){ if(sz[v] > targetsize) return find_centroid(targetsize, v, u); } return u; } const int LIM = 1e6; int mp[LIM+3]; int ans = 1e9+69; int length[int(2e5+3)]; void progress(bool isUpd, int u, int p=-1){ if(isUpd) mp[length[u]] = min(mp[length[u]], depth[u]); else{ int f = desiredLength - length[u]; if(f>=0) ans = min(ans, mp[f]+depth[u]); // cout << u << ' ' << length[u] << ' ' << mp[f] << '+' << depth[u] << '\n'; } for(auto &[v,w] : elen[u]) if(!removed[v] && v!=p){ length[v] = length[u] + w; progress(isUpd, v, u); } } void centroid_decomp(int u=0){ depth[u] = 0; calsize(u); u = find_centroid(sz[u]>>1, u); removed[u] = 1; // cout << "CENTROID " << u << '\n'; memset(mp, 0x3f, sizeof mp); mp[0] = 0; for(auto &[v,w] : elen[u]) if(!removed[v]){ length[v] = w; progress(0, v); progress(1, v); } for(int &v : e[u]) if(!removed[v]) centroid_decomp(v); } int best_path(int _numNode, int _desiredLength, int edge[][2], int edgeLength[]){ numNode = _numNode; desiredLength = _desiredLength; for(int i=0; i<numNode-1; ++i){ e[edge[i][0]].emplace_back(edge[i][1]); e[edge[i][1]].emplace_back(edge[i][0]); elen[edge[i][0]].emplace_back(edge[i][1], edgeLength[i]); elen[edge[i][1]].emplace_back(edge[i][0], edgeLength[i]); } centroid_decomp(); return (ans==1e9+69 ? -1 : ans); } int edge[int(2e5+3)][2]; int edgeLength[int(2e5+3)]; signed main() { cin.tie(0) -> sync_with_stdio(0); int n, k; cin >> n >> k; for(int i=0, u, v; i<n-1; ++i) cin >> edge[i][0] >> edge[i][1]; for(int i=0; i<n-1; ++i) cin >> edgeLength[i]; cout << best_path(n, k, edge, edgeLength); return 0; }

Compilation message (stderr)

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