Submission #1043942

#TimeUsernameProblemLanguageResultExecution timeMemory
1043942GasmaskChanRace (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 { 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); } } } int32_t main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // freopen("test.inp", "r", stdin); freopen("test.out", "w", stdout); int n; cin >> n >> k; for (int u, v, w, i = 1; i < n; i++) { cin >> u >> v >> w; ++u, ++v; g[u].emplace_back(v, w); g[v].emplace_back(u, w); } decompose(1); if (ans == (int)1e18) ans = -1; cout << ans; return 0; }

Compilation message (stderr)

/usr/bin/ld: /tmp/ccwUqQJl.o: in function `main':
race.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccKZGUzh.o:grader.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccKZGUzh.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