Submission #1254343

#TimeUsernameProblemLanguageResultExecution timeMemory
1254343hiepsimauhongRace (IOI11_race)C++20
Compilation error
0 ms0 KiB
#include <bits/stdc++.h> using namespace std; #define int long long const int oo = 1e18; const int N = 200005; int mix = oo; vector<pair<int, int>> a[N]; struct Centroid { int sz[N], high[N], len[N]; bool cen[N]; map<int, int> mp; void DFS(int u, int par) { sz[u] = 1; for (auto [v, w] : a[u]) { if (v == par || cen[v]) continue; DFS(v, u); sz[u] += sz[v]; } } int find_centroid(int u, int par, int total) { for (auto [v, w] : a[u]) { if (v == par || cen[v]) continue; if (sz[v] > total / 2) return find_centroid(v, u, total); } return u; } void DFS_ANS(int u, int par, bool check) { if (high[u] > k) return; if (check) { if (mp.count(k - high[u])) { mix = min(mix, mp[k - high[u]] + len[u]); } } else { if (!mp.count(high[u])) { mp[high[u]] = len[u]; } else { mp[high[u]] = min(mp[high[u]], len[u]); } } for (auto [v, w] : a[u]) { if (v == par || cen[v]) continue; len[v] = len[u] + 1; high[v] = high[u] + w; DFS_ANS(v, u, check); } } void decompose(int u) { DFS(u, -1); int centroid = find_centroid(u, -1, sz[u]); cen[centroid] = true; mp.clear(); mp[0] = 0; high[centroid] = 0; len[centroid] = 0; for (auto [v, w] : a[centroid]) { if (cen[v]) continue; high[v] = w; len[v] = 1; DFS_ANS(v, centroid, true); DFS_ANS(v, centroid, false); } for (auto [v, w] : a[centroid]) { if (!cen[v]) decompose(v); } } int k; void solve(int K) { k = K; decompose(1); } }; Centroid Cen; int best_path(int N, int K, int H[][2], int L[]) { // Clear previous test case data for (int i = 0; i <= N; ++i) { a[i].clear(); Cen.sz[i] = Cen.high[i] = Cen.len[i] = 0; Cen.cen[i] = false; } mix = oo; for (int i = 0; i < N - 1; ++i) { int u = H[i][0] + 1; int v = H[i][1] + 1; int c = L[i]; a[u].emplace_back(v, c); a[v].emplace_back(u, c); } Cen.solve(K); return (mix == oo ? -1 : mix); }

Compilation message (stderr)

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