Submission #986251

#TimeUsernameProblemLanguageResultExecution timeMemory
986251chautanphatRace (IOI11_race)C++14
Compilation error
0 ms0 KiB
#include <bits/stdc++.h> using namespace std; const int N = 2e5 + 1, W = 1e6 + 1; int n, k, child[N], f[W], ans = N; bool del[N]; vector<pair<int, int>> a[N]; void cntSize(int u, int pre = 0) { child[u] = 1; for (int i = 0; i < (int)a[u].size(); i++) { int v = a[u][i].first; if (v == pre || del[v]) continue; cntSize(v, u); child[u] += child[v]; } } int centroid(int u, int sz, int pre = 0) { for (int i = 0; i < (int)a[u].size(); i++) { int v = a[u][i].first; if (v != pre && !del[v] && child[v] > sz/2) return centroid(v, sz, u); } return u; } void cal(int u, int dis, int mode, int pre = 0, int h = 1) { if (dis > k) return; if (!mode) ans = min(ans, h+f[k-dis]); else f[dis] = min(f[dis], h); for (int i = 0; i < (int)a[u].size(); i++) { int v = a[u][i].first, w = a[u][i].second; if (del[v] || v == pre) continue; cal(v, dis+w, mode, u, h+1); } } void reset(int u, int dis, int pre = 0) { f[dis] = N; for (int i = 0; i < (int)a[u].size(); i++) { int v = a[u][i].first, w = a[u][i].second; if (del[v] || v == pre) continue; reset(v, dis+w, u); } } void decompose(int u) { cntSize(u); int root = centroid(u, child[u]); del[root] = 1; for (int i = 0; i < (int)a[root].size(); i++) { int v = a[root][i].first, w = a[root][i].second; if (del[v]) continue; cal(v, w, 0); cal(v, w, 1); } for (int i = 0; i < (int)a[root].size(); i++) { int v = a[root][i].first, w = a[root][i].second; if (del[v]) continue; reset(v, w); } for (int i = 0; i < (int)a[root].size(); i++) if (!del[a[root][i].first]) decompose(a[root][i].first); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> k; for (int i = 1; i <= k; i++) f[i] = N; for (int i = 1; i < n; i++) { int u, v, l; cin >> u >> v >> l; a[++u].push_back({++v, l}); a[v].push_back({u, l}); } decompose(1); cout << (ans == N ? -1 : ans); return 0; }

Compilation message (stderr)

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