제출 #387489

#제출 시각아이디문제언어결과실행 시간메모리
387489saarang123공장들 (JOI14_factories)C++17
0 / 100
39 ms16364 KiB
#include <bits/stdc++.h> #ifndef saarang #include "factories.h" #endif using namespace std; std::mt19937 rng(15); const int mxn = 500 * 1000 + 3, lgn = 20; int up[mxn][lgn], d[mxn], par[mxn], sz[mxn], n; long long dt[mxn], ans[mxn]; vector<array<int, 2>> g[mxn]; bool cent[mxn]; void dfs(int v, int p) { up[v][0] = (p < 0 ? v : p); for(auto &[u, w] : g[v]) if(u != p) { d[u] = d[v] + 1; dt[u] = dt[v] + w; dfs(u, v); } for(int i = 1; i < lgn; i++) up[v][i] = up[up[v][i - 1]][i - 1]; } int kth(int v, int di) { for(int i = 0; i < lgn; i++) if(di >> i & 1) v = up[v][i]; return v; } int lca(int a, int b) { if(d[a] > d[b]) swap(a, b); b = kth(b, d[b] - d[a]); if(a == b) return a; for(int i = lgn - 1; i >= 0; i--) if(up[a][i] != up[b][i]) a = up[a][i], b = up[b][i]; return up[a][0]; } long long dist(int a, int b) { return dt[a] + dt[b] - 2 * dt[lca(a, b)]; } int dfssz(int v, int p) { sz[v] = 1; for(auto &[u, w] : g[v]) if(u != p) sz[v] += dfssz(u, v); return sz[v]; } int fcent(int v, int p) { for(auto &[u, w] : g[v]) if(u != p && !cent[u]) { if(sz[u] > sz[v] / 2) return fcent(u, v); } return v; } void decompose(int v, int p) { dfssz(v, -1); int centroid = fcent(v, -1); cent[centroid] = true; par[centroid] = p; for(auto &[u, w] : g[centroid]) if(u != p && !cent[u]) decompose(u, centroid); } void Init(int N, int A[], int B[], int D[]) { n = N; for(int i = 0; i < n - 1; i++) { g[A[i]].push_back({B[i], D[i]}); g[B[i]].push_back({A[i], D[i]}); } dfs(0, -1); decompose(0, -1); memset(ans, 0x7f, sizeof ans); } void upd(int v) { for(int p = v; p != -1; p = par[p]) ans[p] = min(ans[p], dist(p, v)); } void fix(int v) { for(int p = v; p != -1; p = par[p]) ans[p] = ans[n]; } long long query(int v) { long long res = ans[n]; for(int p = v; p != -1; p = par[p]) res = min(res, ans[p] + dist(p, v)); return res; } long long Query(int S, int X[], int T, int Y[]) { for(int i = 0; i < T; i++) upd(Y[i]); long long answer = ans[n]; for(int i = 0; i < S; i++) answer = min(answer, query(X[i])); for(int i = 0; i < T; i++) fix(Y[i]); return answer; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...