제출 #682766

#제출 시각아이디문제언어결과실행 시간메모리
682766NK_공장들 (JOI14_factories)C++17
100 / 100
3841 ms204792 KiB
// Success consists of going from failure to failure without loss of enthusiasm #include <bits/stdc++.h> #include "factories.h" using namespace std; #define nl '\n' using ll = long long; using E = array<int, 2>; const int nax = 5e5+5; const int LG = 20; vector<E> adj[nax]; bool vis[nax]; int up[nax][LG]; ll DST[nax][LG]; int par[nax], siz[nax], dep[nax]; ll dx[nax], dy[nax], dst[nax]; const ll INFL = ll(1e18) + 10; // START OF LCA void dfs(int u = 0, int p = -1) { up[u][0] = (p == -1 ? u : p); for(int i = 1; i < LG; i++) up[u][i] = up[up[u][i-1]][i-1]; for(auto e : adj[u]) if (e[0] != p) { int v = e[0], w = e[1]; dst[v] = dst[u] + w; dep[v] = dep[u] + 1; dfs(v, u); } } int jmp(int u, int d) { for(int i = 0; i < LG; i++) if ((d>>i) & 1) u = up[u][i]; return u; } int lca(int a, int b) { if (dep[a] > dep[b]) swap(a, b); b = jmp(b, dep[b] - dep[a]); if (a == b) return a; for(int i = LG - 1; i >= 0; i--) if (up[a][i] != up[b][i]) a = up[a][i], b = up[b][i]; return up[a][0]; } ll dist(int u, int v) { return dst[u] + dst[v] - 2LL * dst[lca(u, v)]; } // END OF LCA // START OF CENTROID DECOMPOSITION int find_size(int u, int p = -1) { if (vis[u]) return 0; siz[u] = 1; for(auto e : adj[u]) if (e[0] != p) { int v = e[0]; siz[u] += find_size(v, u); } return siz[u]; } int find_centroid(int u, int p, int n) { for(auto e : adj[u]) if (e[0] != p) { int v = e[0]; if (!vis[v] && siz[v] > n / 2) return find_centroid(v, u, n); } return u; } vector<int> anc; void init_centroid(int u = 0, int p = -1) { find_size(u); int c = find_centroid(u, -1, siz[u]); vis[c] = 1; par[c] = p; for(int i = 0; i < int(size(anc)); i++) { int J = int(size(anc)) - i; // cout << J << " " << anc[i] << " " << dist(c, anc[i]) << endl; DST[c][J] = dist(c, anc[i]); } anc.push_back(c); for(auto e : adj[c]) { int v = e[0]; if (vis[v]) continue; init_centroid(v, c); } anc.pop_back(); } // END OF CENTROID DECOMPOSITION void Init(int N, int A[], int B[], int D[]) { for(int i = 0; i < N; i++) { vis[i] = 0; par[i] = -1; dx[i] = dy[i] = INFL; adj[i] = {}; dst[i] = dep[i] = siz[i] = 0; for(int j = 0; j < LG; j++) up[i][j] = 0; } for(int i = 0; i < N-1; i++) { adj[A[i]].push_back({B[i], D[i]}); adj[B[i]].push_back({A[i], D[i]}); } dfs(); init_centroid(); } vector<int> alt; ll Query(int S, int X[], int T, int Y[]) { for(int i = 0; i < S; i++) { int u = X[i]; dx[u] = 0; alt.push_back(u); int jump = 0; while(par[u] != -1) { u = par[u]; alt.push_back(u); dx[u] = min(dx[u], DST[X[i]][++jump]); } } ll ans = INFL; for(int i = 0; i < T; i++) { int u = Y[i]; int jump = 0; while(u != -1) { ans = min(ans, dx[u] + DST[Y[i]][jump++]); u = par[u]; } } for(const auto &u : alt) dx[u] = INFL; alt.clear(); return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...