제출 #227854

#제출 시각아이디문제언어결과실행 시간메모리
227854tri공장들 (JOI14_factories)C++14
18 / 100
8013 ms110916 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef pair<int, int> pi; typedef pair<ll, ll> pl; typedef vector<int> vi; typedef vector<ld> vd; typedef vector<ll> vl; #define pb push_back #define f first #define s second const int LOGN = 19; const int MAXN = 5e5 + 100; const ll INF = 1e15; vector<pi> aL[MAXN]; int anc[MAXN][LOGN]; int depth[MAXN]; ll rDist[MAXN]; int N; void dfs(int cV, int pV) { for (pi aE : aL[cV]) { int aV = aE.f; ll eC = aE.s; if (aV != pV) { depth[aV] = depth[cV] + 1; rDist[aV] = rDist[cV] + eC; dfs(aV, cV); anc[aV][0] = cV; } } } void prep() { anc[0][0] = 0; for (int k = 1; k < LOGN; k++) { for (int i = 0; i < N; i++) { anc[i][k] = anc[anc[i][k - 1]][k - 1]; } } } int j(int a, int d) { for (int i = 0; i < LOGN; i++) { if (d & (1 << i)) { a = anc[a][i]; } } return a; } int fLCA(int a, int b) { if (depth[a] > depth[b]) swap(a, b); b = j(b, depth[b] - depth[a]); if (a == b) return a; for (int i = LOGN - 1; i >= 0; i--) { if (anc[a][i] != anc[b][i]) { a = anc[a][i]; b = anc[b][i]; } } return anc[a][0]; } void Init(int iN, int A[], int B[], int D[]) { N = iN; for (int i = 0; i < N; i++) { aL[A[i]].pb({B[i], D[i]}); aL[B[i]].pb({A[i], D[i]}); } depth[0] = rDist[0] = 0; dfs(0, -1); prep(); } ll ans; ll best[MAXN][2]; void dfsAll(int cV, int pV) { for (pi aE : aL[cV]) { int aV = aE.f; ll eC = aE.s; if (aV != pV) { dfsAll(aV, cV); best[cV][0] = min(best[cV][0], best[aV][0] + eC); best[cV][1] = min(best[cV][1], best[aV][1] + eC); } ans = min(ans, best[cV][0] + best[cV][1]); } } ll Query(int S, int X[], int T, int Y[]) { vi x(X, X + S); vi y(Y, Y + T); sort(x.begin(), x.end()); x.erase(unique(x.begin(), x.end()), x.end()); sort(y.begin(), y.end()); x.erase(unique(y.begin(), y.end()), y.end()); S = x.size(), T = y.size(); ans = INF; if (S * T >= 5e4) { for (int i = 0; i < N; i++) { for (int j = 0; j < 2; j++) { best[i][j] = INF; } } for (int i = 0; i < S; i++) { best[x[i]][0] = 0; } for (int i = 0; i < T; i++) { best[y[i]][1] = 0; } dfsAll(0, -1); } else { for (int i = 0; i < S; i++) { for (int j = 0; j < T; j++) { int lca = fLCA(x[i], y[j]); ll cur = rDist[x[i]] + rDist[y[j]] - 2 * rDist[lca]; ans = min(ans, cur); } } } assert(ans >= 0); return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...