Submission #827600

#TimeUsernameProblemLanguageResultExecution timeMemory
827600winthemcut3Race (IOI11_race)C++14
Compilation error
0 ms0 KiB
#include <bits/stdc++.h> #define FastIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0) #define ll long long #define PB push_back #define ALL(v) (v).begin(), (v).end() #define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++) #define FORD(i, b, a) for (int i = (b), _a = (a); i >= _a; i--) #define fi first #define se second #define BIT(x, i) (((x) >> (i)) & 1) using namespace std; /** END OF TEMPLATE **/ const int mxN = 2e5 + 5; const int mxM = 1e6 + 7; int n, k, siz[mxN], h[mxN]; vector< pair<int, int> > g[mxN]; map<ll, int> mp; ll dis[mxN]; int res = 1e9; void predfs(int u, int par) { siz[u] = 1; for(auto &it : g[u]) { int v = it.fi, c = it.se; if(v == par) continue; h[v] = h[u] + 1; dis[v] = 1ll*dis[u] + c; predfs(v, u); siz[u] += siz[v]; } } void add(int u, int anc) { auto tmp = mp.find(k - dis[u] + 2*dis[anc]); if(tmp != mp.end()) res = min(res, h[u] + tmp->se - 2*h[anc]); auto it = mp.find(dis[u]); if(it != mp.end()) it->se = min(it->se, h[u]); else mp[dis[u]] = h[u]; } void update(int u, int par, int anc, bool st) { if(!st) mp.erase(dis[u]); else add(u, anc); for(auto &v : g[u]) if(v.fi != par) update(v.fi, u, anc, st); } void dfs(int u, int par) { int heavy = 0; for(auto &it : g[u]) if(it.fi != par) if(siz[it.fi] > siz[heavy]) heavy = it.fi; for(auto &it : g[u]) { int v = it.fi; if(v == par || v == heavy) continue; dfs(v, u); update(v, u, u, 0); } if(heavy) dfs(heavy, u); for(auto &it : g[u]) { int v = it.fi; if(v == par || v == heavy) continue; update(v, u, u, 1); } add(u, u); } int main() { FastIO; //freopen(".inp", "r", stdin); //freopen(".out", "w", stdout); cin >> n >> k; FOR(i, 1, n-1) { int u, v, c; cin >> u >> v >> c; u++; v++; g[u].PB({v, c}); g[v].PB({u, c}); } predfs(1, 0); dfs(1, 0); if(res == 1e9) cout << -1; else cout << res; return 0; } /* */

Compilation message (stderr)

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