제출 #93473

#제출 시각아이디문제언어결과실행 시간메모리
93473Dat160601공장들 (JOI14_factories)C++14
33 / 100
8042 ms128904 KiB
#include "factories.h" #include <bits/stdc++.h> using namespace std; #define mp make_pair #define pb push_back #define fi first #define se second const int maxN = 5e5 + 7; int n, level[maxN], par[20][maxN], st[maxN], ed[maxN], cnt = 0, sz = 0; long long depth[maxN], ans; pair <int, int> cur[4 * maxN]; vector < pair <int, int> > edge[maxN]; void dfs(int u, int p){ st[u] = ++cnt; for(pair <int, int> to : edge[u]){ int v = to.fi, w = to.se; if(v == p) continue; par[0][v] = u; level[v] = level[u] + 1; depth[v] = depth[u] + w; dfs(v, u); } ed[u] = cnt; } int lca(int u, int v){ if(level[u] > level[v]) swap(u, v); for(int i = 19; i >= 0; i--) if(level[par[i][v]] >= level[u]) v = par[i][v]; for(int i = 19; i >= 0; i--) if(par[i][u] != par[i][v]) u = par[i][u], v = par[i][v]; if(u == v) return u; return par[0][u]; } bool cmp(pair <int, int> x, pair <int, int> y){ return st[x.fi] < st[y.fi]; } void Init(int N, int A[], int B[], int D[]) { n = N; for(int i = 0; i < n - 1; i++){ A[i]++, B[i]++; edge[A[i]].pb(mp(B[i], D[i])); edge[B[i]].pb(mp(A[i], D[i])); } par[0][1] = 1; level[1] = 1; dfs(1, 1); for(int i = 1; i < 20; i++){ for(int j = 1; j <= n; j++){ par[i][j] = par[i - 1][par[i - 1][j]]; } } st[n + 1] = 1e9; } pair <long long, long long> solve(){ int u = cur[cnt].fi; long long A = 1e18, B = 1e18; if(cur[cnt].se == 0) A = min(A, depth[u]); if(cur[cnt].se == 1) B = min(B, depth[u]); cnt++; if(cnt > sz) return mp(A, B); while(cur[cnt].fi == u){ if(cur[cnt].se == 0) A = min(A, depth[u]); if(cur[cnt].se == 1) B = min(B, depth[u]); cnt++; } while(ed[u] >= st[cur[cnt].fi]){ pair <long long, long long> tmp = solve(); A = min(A, tmp.fi), B = min(B, tmp.se); } ans = min(ans, A + B - 2LL * depth[u]); return mp(A, B); } long long Query(int S, int X[], int T, int Y[]) { ans = 1e18; sz = 0; for(int i = 0; i < S; i++) cur[++sz] = mp(X[i] + 1, 0); for(int i = 0; i < T; i++) cur[++sz] = mp(Y[i] + 1, 1); sort(cur + 1, cur + 1 + sz, cmp); int sv = sz; for(int i = 1; i < sv; i++) cur[++sz] = mp(lca(cur[i].fi, cur[i + 1].fi), 2); cur[++sz] = mp(n + 1, 0); sort(cur + 1, cur + 1 + sz, cmp); //for(int i = 1; i <= sz; i++) cout << cur[i].fi << endl; cnt = 1; solve(); return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...