제출 #367187

#제출 시각아이디문제언어결과실행 시간메모리
367187parsabahrami공장들 (JOI14_factories)C++17
100 / 100
7912 ms161612 KiB
#include "factories.h" #include <bits/stdc++.h> using namespace std; typedef long long int ll; typedef pair<int, int> pii; #define SZ(x) (int) x.size() #define F first #define S second const int N = 5e5 + 10; int M[N], from[N], to[N], w[N], P[20][N], H[N], St[N], Ft[N], n, tim; vector<int> adj[N]; ll S[N], dp1[N], dp2[N]; void preDFS(int v, int p = -1) { St[v] = tim++; for (int i = 1; i < 20; i++) P[i][v] = P[i - 1][P[i - 1][v]]; for (int id : adj[v]) { int u = from[id] ^ to[id] ^ v; if (u != p) S[u] = S[v] + w[id], H[u] = H[v] + 1, P[0][u] = v, preDFS(u, v); } Ft[v] = tim; } int getpar(int v, int h) { for (int i = h; i; i -= i & -i) v = P[__builtin_ctz(i)][v]; return v; } int LCA(int v, int u) { if (H[u] < H[v]) swap(u, v); u = getpar(u, H[u] - H[v]); for (int i = 19; ~i; i--) if (P[i][v] != P[i][u]) u = P[i][u], v = P[i][v]; return u == v ? v : P[0][v]; } void downDFS(int v) { if (M[v]) dp1[v] = 0; for (int u : adj[v]) { downDFS(u); if (dp1[u] < 1e18) dp1[v] = min(dp1[v], dp1[u] + S[u] - S[v]); } } void upd(pair<pair<ll, ll>, pair<ll, ll>> &x, ll v, ll y) { x.S = min(x.S, {y, v}); if (x.F > x.S) swap(x.S, x.F); } void upDFS(int v) { if (M[v]) dp2[v] = 0; pair<pair<ll, ll>, pair<ll, ll>> x = {{1e16, 1e16}, {1e16, 1e16}}; upd(x, v, dp2[v]); for (int u : adj[v]) { upd(x, u, dp1[u] + S[u] - S[v]); } for (int u : adj[v]) { if (x.F.S == u) dp2[u] = x.S.F + S[u] - S[v]; else dp2[u] = x.F.F + S[u] - S[v]; dp2[u] = min(dp2[u], (ll) 1e18); } for (int u : adj[v]) upDFS(u); } void Init(int _n, int A[], int B[], int D[]) { n = _n; for (int i = 0; i + 1 < n; i++) { from[i] = A[i], to[i] = B[i], w[i] = D[i]; adj[from[i]].push_back(i); adj[to[i]].push_back(i); } preDFS(0); for (int i = 0; i < n; i++) adj[i] = {}; for (int i = 0; i < n; i++) dp1[i] = dp2[i] = 1e18; } ll Query(int s, int X[], int t, int Y[]) { vector<int> vec; for (int i = 0; i < s; i++) vec.push_back(X[i]); for (int i = 0; i < t; i++) vec.push_back(Y[i]), M[Y[i]] = 1; sort(vec.begin(), vec.end(), [&] (int u, int v) { return St[u] < St[v]; }); int k = SZ(vec); for (int i = 0; i < k; i++) { int p = LCA(vec[i], vec[(i + 1) % k]); vec.push_back(p); } sort(vec.begin(), vec.end(), [&] (int u, int v) { return St[u] < St[v]; }); vec.resize(unique(vec.begin(), vec.end()) - vec.begin()); vector<int> st = {vec[0]}; for (int i = 1; i < SZ(vec); i++) { int v = vec[i]; while (St[st.back()] > St[v] || Ft[v] > Ft[st.back()]) st.pop_back(); assert(SZ(st)); adj[st.back()].push_back(v); st.push_back(v); } downDFS(vec[0]); upDFS(vec[0]); ll ret = 1e18; for (int i = 0; i < s; i++) ret = min(ret, min(dp1[X[i]], dp2[X[i]])); for (int i = 0; i < SZ(vec); i++) dp1[vec[i]] = dp2[vec[i]] = 1e18, adj[vec[i]] = {}; for (int i = 0; i < t; i++) M[Y[i]] = 0; return ret; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...