제출 #1126095

#제출 시각아이디문제언어결과실행 시간메모리
1126095tvgk공장들 (JOI14_factories)C++17
0 / 100
21 ms12608 KiB
#include "factories.h" #include<bits/stdc++.h> using namespace std; #define task "a" #define se second #define fi first #define ll long long #define ii pair<ll, ll> const long mxN = 5e5 + 7; int par[mxN][25], par_Cen[mxN], h[mxN], child[mxN]; bool del[mxN]; ll dis[mxN][25], mn[mxN]; vector<ii> w[mxN]; void Buildlog(int j) { for (int i = 1; i < __lg(h[j]); i++) { par[j][i] = par[par[j][i - 1]][i - 1]; dis[j][i] = dis[j][i - 1] + dis[par[j][i - 1]][i - 1]; } } void Build_LCA(int j) { Buildlog(j); for (ii i : w[j]) { if (h[i.fi]) continue; par[i.fi][0] = j; dis[i.fi][0] = i.se; h[i.fi] = h[j] + 1; Build_LCA(i.fi); } } void Pre(int j, int par) { child[j] = 1; for (ii i : w[j]) { if (del[i.fi] || i.fi == par) continue; Pre(i.fi, j); child[j] += child[i.fi]; } } int Find(int j, int sz) { for (ii i : w[j]) { if (del[i.fi] || child[i.fi] > child[j]) continue; if (child[i.fi] * 2 > sz) return Find(i.fi, sz); } return j; } const ll inf = 1e18; void Centroid(int j, int p) { Pre(j, -1); j = Find(j, child[j]); par_Cen[j] = p; mn[j] = inf; del[j] = 1; for (ii i : w[j]) { if (del[i.fi]) continue; Centroid(i.fi, j); } } void Init(int N, int A[], int B[], int D[]) { for (int i = 0; i < N - 1; i++) { w[A[i]].push_back({B[i], D[i]}); w[B[i]].push_back({A[i], D[i]}); } h[0] = 1; Build_LCA(0); Centroid(0, -1); } ll LCA(int u, int v) { if (h[u] < h[v]) swap(u, v); ll res = 0; for (int i = 19; i >= 0; i--) { if (h[u] - (1 << i) >= h[v]) { res += dis[u][i]; u = par[u][i]; } } if (u == v) return res; for (int i = 19; i >= 0; i--) { if (par[u][i] != par[v][i]) { res += dis[u][i] + dis[v][i]; u = par[u][i]; v = par[v][i]; } } return res + dis[u][0] + dis[v][0]; } long long Query(int S, int X[], int T, int Y[]) { vector<int> ver; for (int i = 0; i < S; i++) { int cur = X[i]; while (cur >= 0) { //cerr << X[i] << " " << cur << " " << LCA(X[i], cur) << '\n'; ver.push_back(cur); mn[cur] = min(mn[cur], LCA(X[i], cur)); cur = par_Cen[cur]; } } ll ans = inf; for (int i = 0; i < T; i++) { int cur = Y[i]; while (cur >= 0) { ans = min(ans, mn[cur] + LCA(Y[i], cur)); cur = par_Cen[cur]; } } for (int i : ver) mn[i] = inf; return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...