제출 #109260

#제출 시각아이디문제언어결과실행 시간메모리
109260pamaj공장들 (JOI14_factories)C++14
0 / 100
42 ms39800 KiB
#include <bits/stdc++.h> #include"factories.h" using namespace std; typedef int_fast64_t ll; #pragma GCC optimize ("Ofast") const int maxn = 5e5 + 10, maxlog = 19; int pai[maxn], h[maxn], block[maxn], last[maxn]; ll ans[maxn], dist[maxn][maxlog]; vector<pair<int, int>> G[maxn]; vector<int> tree[maxn], lista; void find_dist(int v, int p, ll depht) { dist[v][h[v]++] = depht; for(auto u : G[v]) { if(u.first == p or block[u.first]) continue; find_dist(u.first, v, depht + u.second); } } using ii = pair<int, int>; const int inf = 0x3f3f3f3f; int n, k; vector<int> v[maxn]; int sz[maxn]; int cvis[maxn]; int tam(int x, int p) { sz[x] = 1; for (int u : v[x]) { if (cvis[u] or u == p) continue; sz[x] += tam(u, x); } return sz[x]; } int tot; ii best; void split(int x, int p) { int heav = tot - sz[x]; for (int u : v[x]) { if (cvis[u] or u == p) continue; heav = max(heav, sz[u]); split(u, x); } if (best.second > heav) best = {x, heav}; } int centroid(int x) { tot = tam(x, x); best = {0, inf}; split(x, x); return best.first; } int solve(int x) { int cent = centroid(x); cvis[cent] = 1; for (int u : v[cent]) { if (cvis[u]) continue; int p = solve(u); tree[cent].push_back(p); tree[p].push_back(cent); } return cent; } void init(int x, int p) { pai[x] = p; for(auto u : tree[x]) { if(u == p) continue; init(u, x); } } void Init(int N, int A[], int B[], int D[]) { for(int i = 0; i < N - 1; i++) { G[A[i]].push_back({B[i], D[i]}); G[B[i]].push_back({A[i], D[i]}); } int ct = solve(1); init(ct, -1); for(int i = 0; i < maxn; i++) ans[i] = (long long)1e17; } int it; long long Query(int S, int X[], int T, int Y[]) { it++; for(int i = 0; i < S; i++) { int v = X[i]; int x = v; for(int j = h[x] - 1; j >= 0; j--) { if(last[v] != it) { last[v] = it; ans[v] = dist[x][j]; } else ans[v] = min(ans[v], dist[x][j]); v = pai[v]; } } ll resp = 1e16; for(int i = 0; i < T; i++) { int v = Y[i]; int x = v; for(int j = h[x] - 1; j >= 0; j--) { if(last[v] == it) resp = min(resp, ans[v] + dist[x][j]); v = pai[v]; } } return resp; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...