Submission #921975

#TimeUsernameProblemLanguageResultExecution timeMemory
921975406Factories (JOI14_factories)C++17
100 / 100
1800 ms130644 KiB
#include <bits/stdc++.h> #include "factories.h" #define FOR(i, a, b) for (int i = (a); i < (b); ++i) using namespace std; using ar = array<int, 2>; const int64_t INF = 1ll << 60; const int N = 5e5 + 5, LG = 19; int n, T, st[N], fn[N], pr[N][LG]; long long h[N], dist[N]; vector<ar> adj[N]; bool is_anc(int v, int p) { return st[p] <= st[v] && fn[v] <= fn[p]; } void dfs(int v, int p) { pr[v][0] = p; FOR(i, 0, LG - 1) pr[v][i + 1] = pr[pr[v][i]][i]; st[v] = ++T; for (auto [u, w]: adj[v]) if (u != p) { h[u] = h[v] + w; dfs(u, v); } fn[v] = ++T; } int LCA(int u, int v) { if (is_anc(u, v)) return v; if (is_anc(v, u)) return u; for (int i = LG - 1; i >= 0; --i) if (!is_anc(u, pr[v][i])) v = pr[v][i]; assert(!is_anc(u, v) && is_anc(u, pr[v][0])); return pr[v][0]; } void Init(int NV, int A[], int B[], int D[]) { n = NV; FOR(i, 0, n - 1) { adj[A[i]].push_back({B[i], D[i]}); adj[B[i]].push_back({A[i], D[i]}); } dfs(0, 0); fill(dist, dist + N, INF); } int all[2 * N], cand[2 * N]; long long Query(int S, int X[], int T, int Y[]) { FOR(i, 0, S) dist[X[i]] = 0; copy(X, X + S, all); copy(Y, Y + T, all + S); int q = S + T, qq = q - 1; sort(all, all + q, [&](const int u, const int v) {return st[u] < st[v];}); FOR(i, 0, q - 1) all[++qq] = LCA(all[i], all[i + 1]); q = qq + 1; sort(all, all + q, [&](const int u, const int v) {return fn[u] < fn[v];}); int ptr = -1; FOR(i, 0, q) { int t = all[i], w; while (ptr >= 0 && is_anc(w = cand[ptr], t)) { dist[t] = min(dist[t], dist[w] + h[w] - h[t]); --ptr; } cand[++ptr] = all[i]; } reverse(all, all + q); ptr = -1; FOR(i, 0, q) { int t = all[i], w; while (ptr >= 0 && !is_anc(t, w = cand[ptr])) --ptr; if (ptr >= 0) dist[t] = min(dist[t], dist[w] + h[t] - h[w]); cand[++ptr] = all[i]; } long long mn = dist[Y[0]]; FOR(i, 1, T) mn = min(mn, dist[Y[i]]); FOR(i, 0, q) dist[all[i]] = INF; return mn; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...