Submission #372764

#TimeUsernameProblemLanguageResultExecution timeMemory
372764LightningRace (IOI11_race)C++14
Compilation error
0 ms0 KiB
//#pragma GCC optimize("Ofast") //#pragma GCC target("sse,sse2,sse3,sse3,sse4,popcnt,abm,mmx") #include "race.h" #include <iostream> #include <algorithm> #include <vector> #include <cmath> #include <set> #include <map> #include <iomanip> #include <cassert> #include <stack> #include <queue> #include <deque> //#include <ext/pb_ds/assoc_container.hpp> //#include <ext/pb_ds/tree_policy.hpp>- using namespace std; //using namespace __gnu_pbds; typedef long long ll; #define int ll typedef pair <int, int> pii; typedef pair <ll, ll> pll; // template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; // order_of_key (k) : Number of items strictly smaller than k . // find_by_order(k) : K-th element in a set (counting from zero). #define sz(a) (int)a.size() #define all(a) a.begin(), a.end() #define pb push_back #define ppb pop_back #define mkp make_pair #define F first #define S second #define lb lower_bound #define ub upper_bound #define show(a) cerr << #a <<" -> "<< a <<" " #define nl cerr <<"\n" const int MAXN = 2e5 + 5; const int oo = 1e18 + 5; int n, k, h[MAXN][2], l[MAXN]; vector <pii> g[MAXN]; int sz[MAXN], ans = oo; bool del[MAXN]; set <pii> st; void calcSZ(int v, int pr = -1) { sz[v] = 1; for (pii x : g[v]) { int to = x.F; if (to == pr || del[to]) { continue; } calcSZ(to, v); sz[v] += sz[to]; } } int findCentroid(int v, int pr = -1) { for (pii x : g[v]) { int to = x.F; if (to == pr || del[to]) { continue; } if (sz[to] > sz[v] / 2) { sz[v] -= sz[to]; sz[to] += sz[v]; return findCentroid(to, v); } } return v; } void update(int v, int pr, int lvl, int d) { st.insert({d, lvl}); for (pii x : g[v]) { int to = x.F, w = x.S; if (to == pr || del[to]) { continue; } update(to, v, lvl + 1, d + w); } } void query(int v, int pr, int lvl, int d) { auto it = st.lower_bound({k - d, 0ll}); if (it != st.end()) { int d2 = it -> F, lvl2 = it -> S; if (d + d2 == k) { ans = min(ans, lvl + lvl2); } } for (pii x : g[v]) { int to = x.F, w = x.S; if (to == pr || del[to]) { continue; } query(to, v, lvl + 1, d + w); } } void travel(int root) { calcSZ(root); int c = findCentroid(root); st.insert({0, 0}); for (pii x : g[c]) { int to = x.F, w = x.S; if (del[to]) { continue; } query(to, c, 1, w); update(to, c, 1, w); } st.clear(); del[c] = 1; for (pii x : g[c]) { int to = x.F; if (del[to]) { continue; } travel(to); } } int best_path(int N, int K, int H[][2], int L[]) { n = N, k = K; for (int i = 0; i < n-1; ++i) { h[i][0] = H[i][0]; h[i][1] = H[i][1]; } for (int i = 0; i < n-1; ++i) { l[i] = L[i]; int a = h[i][0], b = h[i][1], w = l[i]; g[a].pb({b, w}); g[b].pb({a, w}); } travel(0); if (ans == oo) { return -1; } return ans; } /* 4 3 0 1 1 2 1 3 1 2 4 2 --------------------------- 3 3 0 1 1 2 1 1 -1 --------------------------- 11 12 0 1 0 2 2 3 3 4 4 5 0 6 6 7 6 8 8 9 8 10 3 4 5 4 6 3 2 5 6 7 2 */

Compilation message (stderr)

/tmp/cch6kswz.o: In function `main':
grader.cpp:(.text.startup+0x24): undefined reference to `best_path(int, int, int (*) [2], int*)'
collect2: error: ld returned 1 exit status