Submission #1043946

#TimeUsernameProblemLanguageResultExecution timeMemory
1043946GasmaskChanRace (IOI11_race)C++17
Compilation error
0 ms0 KiB
#include <bits/stdc++.h> using namespace std; #define int long long const int MAX = 2e5 + 5; vector<pair<int, int>> g[MAX]; int k, ans = 1e18; bitset<MAX> deleted; struct cal { unordered_map<int, int> mp; void update(int u, int p, int sum, int depth) { if (sum > k) return; auto &cur = mp[sum]; if (cur == 0) cur = depth; else cur = min(cur, depth); for (auto &[v, w] : g[u]) { if (v != p && !deleted[v]) { update(v, u, sum + w, depth + 1); } } } void add(int u, int p, int sum, int depth) { if (sum > k) return; auto it = mp.find(k - sum); if (it != mp.end()) ans = min(ans, it->second + depth); for (auto &[v, w] : g[u]) { if (v != p && !deleted[v]) { add(v, u, sum + w, depth + 1); } } } void lamviec(int u) { mp[0] = 0; for (auto &[v, w] : g[u]) { if (!deleted[v]) { add(v, u, w, 1); update(v, u, w, 1); } } } }; int sz[MAX]; void dfs(int u, int p) { sz[u] = 1; for (auto &[v, w] : g[u]) { if (v != p && !deleted[v]) { dfs(v, u); sz[u] += sz[v]; } } } int findcentroid(int u, int p, const int &n) { for (auto &[v, w] : g[u]) { if (v != p && !deleted[v] && sz[v] * 2 > n) return findcentroid(v, u, n); } return u; } void decompose(int u) { dfs(u, 0); u = findcentroid(u, 0, sz[u]); deleted[u] = true; cal tmp; tmp.lamviec(u); for (auto &[v, w] : g[u]) { if (!deleted[v]) { decompose(v); } } } int best_path(int N, int K, int H[][2], int L[]) { int n = N; k = K; for (int u, v, w, i = 0; i < n - 1; i++) { u = H[i][0], v = H[i][1], w = L[i]; g[u].emplace_back(v, w); g[v].emplace_back(u, w); } decompose(1); if (ans == (int)1e18) ans = -1; return ans; }

Compilation message (stderr)

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