Submission #1261972

#TimeUsernameProblemLanguageResultExecution timeMemory
1261972hiepsimauhongRace (IOI11_race)C++20
Compilation error
0 ms0 KiB
#include "race.h" #include <bits/stdc++.h> using namespace std; using ll = long long; #define int long long const int oo = 1e18; const int N = 2e5 + 5; int n, k, mix, ans; int d = 0; vector<pair<int,int>> a[N]; struct Centroid{ int sz[N]; int high[N], len[N]; bool cen[N]; map<int, pair<int,int>> mp; void DFS(int u, int par){ sz[u] = 1; for(auto e : a[u]){ int v = e.first; if(v == par || cen[v]){ continue; } DFS(v, u); sz[u] += sz[v]; } } int find_centroid(int u, int par, int mx){ for(auto e : a[u]){ int v = e.first; if(v == par || cen[v]){ continue; } if(sz[v] > mx / 2){ return find_centroid(v, u, mx); } } return u; } void DFS_ANS(int u, int par, bool check){ if(high[u] > k){ return; } if(check){ if(mp[k - high[u]].second != 0){ if(mix > mp[k - high[u]].first + len[u]){ mix = mp[k - high[u]].first + len[u]; } } } else{ auto &x = mp[high[u]]; if(x.first > len[u] || x.second == 0){ x.first = len[u]; x.second = 1; } else if(x.first == len[u]){ x.second++; } } for(auto e : a[u]){ int v = e.first, w= e.second; if(v == par || cen[v]){ continue; } len[v] = len[u] + 1; high[v] = high[u] + w; DFS_ANS(v, u, check); } } void tree(int u){ mp.clear(); DFS(u, -1); int centroid = find_centroid(u, -1, sz[u]); cen[centroid] = true; mp[0].second = 1; high[centroid] = len[centroid] = 0; for(auto e : a[centroid]){ int v = e.first, w = e.second; if(cen[v]) continue; high[v] = w; len[v] = 1; DFS_ANS(v, centroid, 1); DFS_ANS(v, centroid, 0); } for(auto e : a[centroid]){ int v = e.first; if(!cen[v]) tree(v); } } }; Centroid Cen; int best_path(int N, int K, int H[][2], int L[]){ // reset for(int i = 0; i <= N; i++){ a[i].clear(); Cen.sz[i] = Cen.high[i] = Cen.len[i] = 0; Cen.cen[i] = false; } n = N; k = K; mix = oo; ans = 0; // build graph (OJ.uz cho input 0-indexed) for(int i=0;i<N-1;i++){ int u = H[i][0]; int v = H[i][1]; int c = L[i]; a[u].push_back({v, c}); a[v].push_back({u, c}); } Cen.tree(0); if(ans == 0) return -1; return 2 * ans; }

Compilation message (stderr)

/usr/bin/ld: /tmp/ccGOVqR2.o: in function `main':
grader.cpp:(.text.startup+0x28): undefined reference to `best_path(int, int, int (*) [2], int*)'
collect2: error: ld returned 1 exit status