Submission #230370

#TimeUsernameProblemLanguageResultExecution timeMemory
230370arborFactories (JOI14_factories)C++14
100 / 100
4969 ms171996 KiB
#include <bits/stdc++.h> #define all(x) x.begin(), x.end() #define lc (i << 1) #define rc (i << 1 | 1) using namespace std; using ll = long long; using pii = pair<int, int>; const int MN = 5e5 + 5, LN = 19, MOD = 1e9 + 7, INF = 0x3f3f3f3f, BSZ = 320; vector<pii> g[MN]; int sz[MN], par[MN], lvl[MN]; ll down[LN][MN]; // dis from a centroid at lvl j, to a node i bool vis[MN]; ll mn[MN]; // mn dis from centroid i, to any factory of first kind in children int qid[MN], id = 1; int get_sz(int u, int p) { sz[u] = 1; for (pii e : g[u]) if (e.first != p && !vis[e.first]) sz[u] += get_sz(e.first, u); return sz[u]; } int centroid(int u, int p, int s) { for (pii e : g[u]) if (e.first != p && !vis[e.first] && sz[e.first] > s / 2) return centroid(e.first, u, s); return u; } void dfs(int u, int p, ll dis, int d) { down[d][u] = dis; for (pii e : g[u]) if (e.first != p && !vis[e.first]) dfs(e.first, u, dis + e.second, d); } void go(int u, int p, int d) { int s = get_sz(u, -1); int c = centroid(u, -1, s); par[c] = p; lvl[c] = d; dfs(c, -1, 0, d); vis[c] = true; for (pii e : g[c]) { if (!vis[e.first]) { go(e.first, c, d + 1); } } } void Init(int N, int A[], int B[], int D[]) { for (int i = 0; i < N - 1; i++) { int u = A[i], v = B[i], w = D[i]; g[u].emplace_back(v, w); g[v].emplace_back(u, w); } memset(down, 0x3f, sizeof(down)); go(0, -1, 0); } long long Query(int S, int X[], int T, int Y[]) { for (int i = 0; i < S; i++) { int cur = X[i]; while (cur != -1) { if (qid[cur] != id) qid[cur] = id, mn[cur] = down[lvl[cur]][X[i]]; else mn[cur] = min(mn[cur], down[lvl[cur]][X[i]]); cur = par[cur]; } } ll ret = LLONG_MAX; for (int i = 0; i < T; i++) { int cur = Y[i]; while (cur != -1) { if (qid[cur] == id) ret = min(ret, mn[cur] + down[lvl[cur]][Y[i]]); cur = par[cur]; } } id++; return ret; } /* int main() { int N, Q; cin >> N >> Q; int a[N + 1], b[N + 1], d[N + 1]; for (int i = 0; i < N - 1; i++) cin >> a[i] >> b[i] >> d[i]; Init(N, a, b, d); for (int i = 0; i < Q; i++) { int s, t; cin >> s >> t; int x[s + 1], y[t + 1]; for (int j = 0; j < s; j++) cin >> x[j]; for (int j = 0; j < t; j++) cin >> y[j]; cout << Query(s, x, t, y) << '\n'; } return 0; } */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...