Submission #969511

#TimeUsernameProblemLanguageResultExecution timeMemory
969511TurkhuuFactories (JOI14_factories)C++17
15 / 100
8055 ms149396 KiB
#include "factories.h" #include <bits/stdc++.h> using namespace std; using ll = long long; int N; vector<ll> len, best; vector<int> p, sz, vis, dep; vector<vector<int>> par; vector<vector<array<int, 2>>> adj; void dfs(int x, int p) { for (int i = 0; i < 18 && par[x][i] != -1; i++) { par[x][i + 1] = par[par[x][i]][i]; } for (auto [y, z] : adj[x]) { if (y == p) continue; par[y][0] = x; dep[y] = dep[x] + 1; len[y] = len[x] + z; dfs(y, x); } } void init(int x, int p) { sz[x] = 1; for (auto [y, z] : adj[x]) { if (vis[y] || y == p) continue; init(y, x); sz[x] += sz[y]; } } int find(int x, int p, int s) { for (auto [y, z] : adj[x]) { if (vis[y] || y == p) continue; if (sz[y] * 2 > s) return find(y, x, s); } return x; } int cd(int x) { init(x, -1); x = find(x, -1, sz[x]); vis[x] = 1; for (auto [y, z] : adj[x]) { if (!vis[y]) { p[cd(y)] = x; } } return x; } int lca(int x, int y) { if (dep[x] < dep[y]) swap(x, y); for (int i = 0; i < 19; i++) { if ((dep[x] - dep[y]) >> i & 1) { x = par[x][i]; } } if (x == y) return x; for (int i = 18; i >= 0; i--) { if (par[x][i] != par[y][i]) { x = par[x][i]; y = par[y][i]; } } return par[x][0]; } ll dis(int x, int y) { return len[x] + len[y] - 2 * len[lca(x, y)]; } void Init(int n, int A[], int B[], int D[]) { N = n; p.resize(N, -1); sz.resize(N); vis.resize(N); adj.resize(N); dep.resize(N); len.resize(N); par.resize(N, vector<int>(19, -1)); best.resize(N, 1e18); 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(0, -1); cd(0); } 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 = p[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 = p[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 = p[j]) { best[j] = 1e18; } } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...