제출 #558157

#제출 시각아이디문제언어결과실행 시간메모리
558157Neos공장들 (JOI14_factories)C++17
15 / 100
8058 ms146796 KiB
#include"factories.h" #include <bits/stdc++.h> using namespace std; using ll = long long; using ld = long double; using ull = unsigned long long; using ii = pair<int, int>; #define fi first #define se second #define pb push_back #define numBit(x) (__builtin_popcountll(1ll * (x))) #define getBit(x, i) ((x) >> (i) & 1) #define sz(x) (int)x.size() #define all(x) x.begin(), x.end() template<class X, class Y> bool minimize(X &x, const Y &y) { X eps = 1e-9; if (x > y + eps) { x = y; return true; } else return false; } template<class X, class Y> bool maximize(X &x, const Y &y) { X eps = 1e-9; if (x + eps < y) { x = y; return true; } else return false; } const int N = 5e5 + 7, LOG = 20; long long oo = 1e18 + 7; //sample program int n, m, sz[N], par[N], P[N][LOG]; ll ans[N], d[N], h[N]; bool done[N]; vector<ii> adj[N]; void get_sz(int u, int par) { sz[u] = 1; for (auto [v, w]: adj[u]) if (v != par && !done[v]) { get_sz(v, u); sz[u] += sz[v]; } } int centroid(int u, int par, int n) { for (auto [v, w]: adj[u]) if (v != par && !done[v] && sz[v] * 2 > n) return centroid(v, u, n); return u; } int solve(int u) { get_sz(u, -1); int rt = centroid(u, -1, sz[u]); done[rt] = 1; for (auto [v, w]: adj[rt]) if (!done[v]) par[solve(v)] = rt; return rt; } void dfs(int u) { for (int i = 1; i < LOG; i++) P[u][i] = P[P[u][i - 1]][i - 1]; for (auto [v, w]: adj[u]) if (v != P[u][0]) P[v][0] = u, h[v] = h[u] + 1, d[v] = d[u] + w, dfs(v); } int lca(int u, int v) { if (h[u] < h[v]) swap(u, v); for (int i = LOG - 1; i >= 0; i--) if (h[u] - (1 << i) >= h[v]) u = P[u][i]; if (u == v) return u; for (int i = LOG - 1; i >= 0; i--) if (P[u][i] && P[u][i] != P[v][i]) u = P[u][i], v = P[v][i]; return P[u][0]; } long long dis(int u, int v) { return d[u] + d[v] - 2 * d[lca(u, v)]; } void Init(int N, int A[], int B[], int D[]){ n = N; fill(ans, ans + n, oo); for (int i = 0; i < n - 1; i++) { adj[A[i]].pb(ii(B[i], D[i])); adj[B[i]].pb(ii(A[i], D[i])); } par[solve(0)] = -1; dfs(0); } void upd(int u, bool t) { for (int v = u; v >= 0; v = par[v]) if (t) minimize(ans[v], dis(u, v)); else ans[v] = oo; } long long get(int u) { long long res = oo; for (int v = u; v >= 0; v = par[v]) minimize(res, ans[v] + dis(u, v)); return res; } long long Query(int S, int X[], int T, int Y[]) { long long res = 1e18; for (int i = 0; i < S; i++) upd(X[i], 1); for (int i = 0; i < T; i++) minimize(res, get(Y[i])); for (int i = 0; i < S; i++) upd(X[i], 0); return res; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...