제출 #88117

#제출 시각아이디문제언어결과실행 시간메모리
88117KCSC공장들 (JOI14_factories)C++14
33 / 100
8064 ms409484 KiB
#ifndef HOME #include "factories.h" #endif #include <bits/stdc++.h> using namespace std; const int LOG = 21; const int DIM = 500005; int lev[DIM], szt[DIM], par[DIM], rmq[LOG][DIM << 1], pwr[DIM << 1], pos[DIM]; long long dst[DIM], dp[DIM]; vector<pair<int, int>> edg[DIM]; bool oki[DIM]; void dfs(int x, int f, int d) { static int nr = 0; dst[x] = dst[f] + d; rmq[0][++nr] = x; lev[x] = lev[f] + 1; pos[x] = nr; for (auto &ed : edg[x]) { int y = ed.first, c = ed.second; if (y != f) { dfs(y, x, c); rmq[0][++nr] = x; } } } void getCentroid(int x, int f, int sz, int &c) { int mx = 0; szt[x] = 1; for (auto &ed : edg[x]) { int y = ed.first; if (!oki[y] and y != f) { getCentroid(y, x, sz, c); szt[x] += szt[y]; mx = max(mx, szt[y]); } } mx = max(mx, sz - szt[x]); if (mx <= sz / 2) { c = x; } } void buildRmq(int n) { for (int i = 2; i <= n; ++i) { pwr[i] = pwr[i >> 1] + 1; } for (int k = 1; (1 << (k - 1)) < n; ++k) { for (int i = 1, j = (1 << (k - 1)) + 1; j <= n; ++i, ++j) { if (lev[rmq[k - 1][i]] < lev[rmq[k - 1][j]]) { rmq[k][i] = rmq[k - 1][i]; } else { rmq[k][i] = rmq[k - 1][j]; } } } } int lca(int x, int y) { x = pos[x]; y = pos[y]; if (x > y) { swap(x, y); } int p = pwr[y - x + 1]; if (lev[rmq[p][x]] < lev[rmq[p][y - (1 << p) + 1]]) { return rmq[p][x]; } else { return rmq[p][y - (1 << p) + 1]; } } long long getDist(int x, int y) { return dst[x] + dst[y] - dst[lca(x, y)] * 2; } void getTree(int x, int f, int sz) { getCentroid(x, f, sz, x); getCentroid(x, f, sz, x); par[x] = f; dp[x] = (1LL << 60); oki[x] = true; for (auto &ed : edg[x]) { int y = ed.first; if (!oki[y]) { getTree(y, x, szt[y]); } } } void Init(int n, int a[], int b[], int d[]) { for (int i = 0; i < n - 1; ++i) { int x = ++a[i], y = ++b[i], c = d[i]; edg[x].push_back(make_pair(y, c)); edg[y].push_back(make_pair(x, c)); } dfs(1, 0, 0); buildRmq((n << 1) - 1); getTree(1, 0, n); } long long Query(int s, int a[], int t, int b[]) { long long ans = (1LL << 60); for (int i = 0; i < s; ++i) { for (int x = ++a[i]; x; x = par[x]) { dp[x] = min(dp[x], getDist(x, a[i])); } } for (int i = 0; i < t; ++i) { for (int x = ++b[i]; x; x = par[x]) { ans = min(ans, dp[x] + getDist(x, b[i])); } } for (int i = 0; i < s; ++i) { for (int x = a[i]; x; x = par[x]) { dp[x] = (1LL << 60); } } return ans; } #ifdef HOME int main(void) { freopen("factories.in", "r", stdin); freopen("factories.out", "w", stdout); int n, q; cin >> n >> q; int a[100], b[100], d[100]; for (int i = 0; i < n - 1; ++i) { cin >> a[i] >> b[i] >> d[i]; } Init(n, a, b, d); while (q--) { int s, t; cin >> s >> t; for (int i = 0; i < s; ++i) { cin >> a[i]; } for (int i = 0; i < t; ++i) { cin >> b[i]; } cout << Query(s, a, t, b) << "\n"; } return 0; } #endif
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...