제출 #66982

#제출 시각아이디문제언어결과실행 시간메모리
66982imeimi2000공장들 (JOI14_factories)C++17
100 / 100
3020 ms295328 KiB
#include "factories.h" #include <vector> #include <algorithm> #include <functional> using namespace std; typedef long long llong; typedef pair<int, int> pii; typedef pair<llong, llong> pll; struct _edge { int x, d; _edge(int x, int d) : x(x), d(d) {} }; int n, k; vector<_edge> edge[500001]; int dep[500001]; llong dist[500001]; int st[500001]; int ed[500001]; int ord[1000000]; pii seg[1000000][21]; int pw[1000001]; int sz; void dfs(int x, int p) { ord[st[x] = k++] = x; for (_edge i : edge[x]) { if (i.x == p) continue; dep[i.x] = dep[x] + 1; dist[i.x] = dist[x] + i.d; dfs(i.x, x); ord[k++] = x; } ed[x] = k; } void init() { for (int i = 1, j = 0; i <= 1000000; ++i) { if ((1 << (j + 1)) < i) ++j; pw[i] = j; } for (int i = 0; i < k; ++i) { seg[i][0] = pii(dep[ord[i]], ord[i]); } for (int i = 1; i < 21; ++i) { for (int j = 0; j < k; ++j) { seg[j][i] = seg[j][i - 1]; if (j + (1 << (i - 1)) < k) { seg[j][i] = min(seg[j][i], seg[j + (1 << (i - 1))][i - 1]); } } } } 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]].emplace_back(B[i], D[i]); edge[B[i]].emplace_back(A[i], D[i]); } dfs(1, 0); init(); } int lca(int x, int y) { if (x == y) return x; x = st[x]; y = st[y]; if (x > y) swap(x, y); int t = pw[y - x + 1]; return min(seg[x][t], seg[y - (1 << t) + 1][t]).second; } const llong inf = 1e16; int in[500001]; int m, idx; int qs[1000000]; llong ans; pll dfs2() { llong d = dist[qs[idx]]; llong mx = d + ((in[qs[idx]] == 1) ? 0 : inf); llong my = d + ((in[qs[idx]] == 2) ? 0 : inf); int e = ed[qs[idx++]]; while (idx < m) { if (e < st[qs[idx]]) break; llong rx, ry; tie(rx, ry) = dfs2(); ans = min({ ans, mx + ry - d - d, my + rx - d - d }); mx = min(mx, rx); my = min(my, ry); } return pll(mx, my); } llong Query(int S, int X[], int T, int Y[]) { m = 0; for (int i = 0; i < S; ++i) { qs[m++] = ++X[i]; } for (int i = 0; i < T; ++i) { qs[m++] = ++Y[i]; } sort(qs, qs + m, [&](int i, int j) { return st[i] < st[j]; }); for (int i = 0; i + 1 < m; ++i) { qs[m + i] = lca(qs[i], qs[i + 1]); } m = (m << 1) - 1; sort(qs, qs + m, [&](int i, int j) { return st[i] < st[j]; }); m = unique(qs, qs + m) - qs; for (int i = 0; i < m; ++i) in[qs[i]] = 0; for (int i = 0; i < S; ++i) in[X[i]] = 1; for (int i = 0; i < T; ++i) in[Y[i]] = 2; idx = 0; ans = inf; dfs2(); return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...