Submission #1046534

#TimeUsernameProblemLanguageResultExecution timeMemory
1046534TurkhuuFactories (JOI14_factories)C++17
100 / 100
2281 ms196760 KiB
#include "factories.h" #include <bits/stdc++.h> using namespace std; using ll = long long; int N; vector<vector<pair<int, int>>> adj; vector<vector<int>> s; vector<int> dep, euler, pos, lg, sz, par, vis; vector<ll> d2r, best; void dfs(int x, int p) { pos[x] = euler.size(); euler.push_back(x); for (auto [y, z] : adj[x]) { if (y == p) continue; dep[y] = dep[x] + 1; d2r[y] = d2r[x] + z; dfs(y, x); euler.push_back(x); } } int f(int i, int j) { return (i != -1 && (j == -1 || dep[i] < dep[j])) ? i : j; } void build() { int n = euler.size(); s.resize(lg[n] + 1); s[0] = euler; for (int i = 0; i < lg[n]; i++) { s[i + 1].resize(n - (2 << i) + 1); for (int j = 0; j + (2 << i) <= n; j++) { s[i + 1][j] = f(s[i][j], s[i][j + (1 << i)]); } } } int lca(int a, int b) { a = pos[a], b = pos[b]; if (a > b) swap(a, b); b++; int k = lg[b - a]; return f(s[k][a], s[k][b - (1 << k)]); } ll dis(int a, int b) { return d2r[a] + d2r[b] - 2 * d2r[lca(a, b)]; } void init(int x, int p) { sz[x] = 1; for (auto [y, z] : adj[x]) { if (y == p || vis[y]) continue; init(y, x); sz[x] += sz[y]; } } int find(int x, int p, int n) { for (auto [y, z] : adj[x]) { if (y == p || vis[y]) continue; if (sz[y] * 2 > n) return find(y, x, n); } return x; } int cd(int x) { init(x, -1); vis[x = find(x, -1, sz[x])] = 1; for (auto [y, z] : adj[x]) { if (!vis[y]) par[cd(y)] = x; } return x; } void Init(int n, int A[], int B[], int D[]) { N = n; sz.resize(N); adj.resize(N); dep.resize(N); pos.resize(N); d2r.resize(N); vis.resize(N); par.resize(N); best.resize(N, 1e18); lg.resize(2 * N); for (int i = 2; i < 2 * N; i++) lg[i] = lg[i / 2] + 1; for (int i = 0; i < N - 1; i++) { adj[A[i]].emplace_back(B[i], D[i]); adj[B[i]].emplace_back(A[i], D[i]); } dfs(0, -1); build(); par[cd(0)] = -1; } ll Query(int S, int X[], int T, int Y[]) { for (int i = 0; i < S; i++) { for (int j = X[i]; j != -1; j = par[j]) { best[j] = min(best[j], dis(j, X[i])); } } ll ans = 1e18; for (int i = 0; i < T; i++) { for (int j = Y[i]; j != -1; j = par[j]) { ans = min(ans, best[j] + dis(j, Y[i])); } } for (int i = 0; i < S; i++) { for (int j = X[i]; j != -1; j = par[j]) { best[j] = 1e18; } } return ans; }

Compilation message (stderr)

factories.cpp: In function 'int lca(int, int)':
factories.cpp:37:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   37 |     if (a > b) swap(a, b); b++;
      |     ^~
factories.cpp:37:28: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   37 |     if (a > b) swap(a, b); b++;
      |                            ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...