Submission #1261982

#TimeUsernameProblemLanguageResultExecution timeMemory
1261982hiepsimauhongRace (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; #define quickly ios_base::sync_with_stdio(0);cin.tie(0); cout.tie(0); #define print(a,l,r) for(int OK(l); OK <= r ; ++OK){ if(a[OK] < oo){cout << a[OK] <<' ';} else{cout << "- ";}} cout << '\n'; #define prints(a) for(auto i : a){ cout << i <<' ';} cout << '\n'; #define printz(a,l,r) for(int OK(1) ; OK <= l ; ++OK){for(int KO(1) ; KO <= r ; ++KO){if(a[OK][KO] < oo){cout << a[OK][KO] <<' ';}else{cout << "- ";}}cout << '\n';} cout << '\n'; #define fs first #define sd second #define ii pair<int, int> #define iii pair<int, ii> #define all(a) a.begin(), a.end() const int N = 2e5 + 5; const int mod = 1e9 + 7; int n, k, mix = oo, ans(0); int d = 0; vector<ii> a[N]; struct Centroid{ int sz[N]; int high[N], len[N]; bool cen[N]; map<int, ii> mp; void DFS(int u, int par){ sz[u] = 1; for(ii e : a[u]){ int v = e.fs; if(v == par || cen[v]){ continue; } DFS(v, u); sz[u] += sz[v]; } } int find_centroid(int u, int par, int mx){ for(ii e : a[u]){ int v = e.fs; 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(check){ if(mp[k - high[u]].sd != 0){ if(mix > mp[k - high[u]].fs + len[u]){ mix = mp[k - high[u]].fs + len[u]; ans = 0; d = mp[k - high[u]].sd; } else if(mix == mp[k - high[u]].fs + len[u]){ d += mp[k - high[u]].sd; } } } else{ ii &x = mp[high[u]]; if(x.fs > len[u] || x.sd == 0){ x.fs = len[u]; x.sd = 1; } else if(x.sd == len[u]){ x.sd++; } } for(ii e : a[u]){ int v = e.fs, w= e.sd; 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){ // tim centroid mp.clear(); DFS(u, -1); int centroid = find_centroid(u, -1, sz[u]); cen[centroid] = true; d = 0; mp[0].sd = 1; high[centroid] = len[centroid] = 0; // tim dap an for(ii e : a[centroid]){ int v = e.fs, w = e.sd; if(cen[v]){ continue; } high[v] = w; len[v] = 1; DFS_ANS(v, centroid, 1); DFS_ANS(v, centroid, 0); } ans += d; // Con con nho hon for(ii e : a[centroid]){ int v = e.fs, w = e.sd; if(cen[v]){ continue; } tree(v); } } }; Centroid Cen; int best_path(int _N, int _K, int H[][2], int L[]){ n = _N; k = _K; for(int i(0) ; i < n - 1 ; ++i){ int u, v, c; u = H[i][0], v = H[i][1], c = L[i]; a[u + 1].push_back({v + 1, c}); a[v + 1].push_back({u + 1, c}); } Cen.tree(1); if(ans == 0){ return -1; } return 2 * ans; }

Compilation message (stderr)

/usr/bin/ld: /tmp/cckBIucG.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