제출 #683199

#제출 시각아이디문제언어결과실행 시간메모리
683199LucaGreg공장들 (JOI14_factories)C++17
100 / 100
6514 ms205476 KiB
#include <bits/stdc++.h> #include "factories.h" using namespace std; #define pb push_back #define ll long long int #define ff first #define ss second const ll INF = 1000000000000000000; vector<int> adj[1000010]; vector<int> weight[1000010]; bool removed[1000010]; int sub[1000010]; int paiCentroid[1000010]; pair<ll, int> minFactoryDist[1000010]; int ancestor[1000010][30]; ll nivel[1000010]; int tin[1000010], tout[1000010]; int h = 0; int tempo = 0; int curQuery = 0; void dfsInit(int cur, int pai){ sub[cur] = 1; for(int i=0;i<(int)adj[cur].size();i++){ int viz = adj[cur][i]; if(removed[viz]) continue; if(viz==pai) continue; dfsInit(viz, cur); sub[cur] += sub[viz]; } } int findCentroid(int cur, int pai, int size){ for(int i=0;i<(int)adj[cur].size();i++){ int viz = adj[cur][i]; if(removed[viz]) continue; if(viz==pai) continue; if(sub[viz]>size/2) return findCentroid(viz, cur, size); } return cur; } void createCentroidTree(int cur, int centroidPai){ dfsInit(cur, cur); int centroid = findCentroid(cur, cur, sub[cur]); paiCentroid[centroid] = centroidPai; removed[centroid] = true; for(int i=0;i<(int)adj[centroid].size();i++){ int viz = adj[centroid][i]; if(removed[viz]) continue; createCentroidTree(viz, centroid); } } void dfs(int cur, int pai){ tempo++; tin[cur] = tempo; ancestor[cur][0] = pai; for(int i=1;i<=h;i++) ancestor[cur][i] = ancestor[ancestor[cur][i-1]][i-1]; for(int i=0;i<(int)adj[cur].size();i++){ int viz = adj[cur][i]; int w = weight[cur][i]; if(viz==pai) continue; nivel[viz] = nivel[cur] + w; dfs(viz, cur); } tout[cur] = tempo; } bool isAncestor(int a, int b){ return tin[a]<=tin[b] && tout[b]<=tout[a]; } int lca(int a, int b){ if(isAncestor(a, b)) return a; if(isAncestor(b, a)) return b; for(int i=h;i>=0;i--) if(!isAncestor(ancestor[a][i], b)) a = ancestor[a][i]; return ancestor[a][0]; } ll calculaDist(int a, int b){ int lca_ = lca(a, b); ll resp = abs(nivel[lca_] - nivel[a]) + abs(nivel[lca_] - nivel[b]); return resp; } void update(int v){ int cur = v; while(cur!=-1){ ll distancia = calculaDist(v, cur); if(minFactoryDist[cur].ss<curQuery){ minFactoryDist[cur].ff = distancia; minFactoryDist[cur].ss = curQuery; }else{ minFactoryDist[cur].ff = min(minFactoryDist[cur].ff, distancia); } cur = paiCentroid[cur]; } } ll calculaMinFactoryDist(int v){ int cur = v; ll resp = INF; while(cur!=-1){ ll distancia = calculaDist(v, cur); if(minFactoryDist[cur].ss==curQuery) resp = min(resp, distancia + minFactoryDist[cur].ff); cur = paiCentroid[cur]; } return resp; } void Init(int N, int A[], int B[], int D[]){ for(int i=0;i<N-1;i++){ int a = A[i], b = B[i], d = D[i]; adj[a].pb(b); weight[a].pb(d); adj[b].pb(a); weight[b].pb(d); } nivel[0] = 0; h = ceil(log2(N)); dfs(0, 0); createCentroidTree(0, -1); } long long Query(int S, int X[], int T, int Y[]){ curQuery++; for(int i=0;i<S;i++) update(X[i]); //for(int i=0;i<7;i++) printf("%d %d %d %d\n", i, nivel[i], minFactoryDist[i].ff, minFactoryDist[i].ss); ll resp = INF; for(int i=0;i<T;i++) resp = min(resp, calculaMinFactoryDist(Y[i])); return resp; } /*int main() { int n, q; scanf("%d %d", &n, &q); int a[100010], b[100010], d[100010]; for(int i=0;i<n-1;i++) scanf("%d %d %d", &a[i], &b[i], &d[i]); Init(n, a, b, d); for(int i=0;i<q;i++){ int s, t; scanf("%d %d", &s, &t); int x[10010], y[10010]; for(int j=0;j<s;j++) scanf("%d", &x[j]); for(int j=0;j<t;j++) scanf("%d", &y[j]); printf("%lld\n", Query(s, x, t, y)); } return 0; }*/
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...