제출 #563690

#제출 시각아이디문제언어결과실행 시간메모리
563690hibiki공장들 (JOI14_factories)C++11
15 / 100
8053 ms155616 KiB
#include"factories.h" #include<bits/stdc++.h> using namespace std; #define pb push_back #define f first #define s second // global int n; vector<pair<int,long long> > v[500005]; // centroid int cen[500005],sz[500005],deep[500005]; long long mn[500005],dist[500005][20]; int re_size(int nw,int fa) { sz[nw] = 1; for(auto go: v[nw]) if(go.f != fa && cen[go.f] == -1) sz[nw] += re_size(go.f,nw); return sz[nw]; } int fi_cen(int nw,int fa,int sum) { for(auto go: v[nw]) if(go.f != fa && cen[go.f] == -1 && sz[go.f] > sum / 2) return fi_cen(go.f,nw,sum); return nw; } void get_dist(int nw,int fa,int lv) { for(auto go: v[nw]) { if(go.f != fa && cen[go.f] == -1) { dist[go.f][lv] = dist[nw][lv] + go.s; get_dist(go.f,nw,lv); } } } void centroid_decomp(int nw,int fa) { int c = fi_cen(nw, -1, re_size(nw, -1)); if(fa == -2) deep[c] = 0; else deep[c] = deep[fa] + 1; cen[c] = fa; get_dist(c, -1, deep[c]); for(auto go: v[c]) if(go.f != fa && cen[go.f] == -1) centroid_decomp(go.f, c); } void cen_upd(int nw) { int cur = nw; while(cur != -2) { mn[cur] = min(mn[cur],dist[nw][deep[cur]]); cur = cen[cur]; } } long long cen_query(int nw) { int cur = nw; long long ret = 1e18; while(cur != -2) { if(mn[cur] != 1e18) ret = min(ret,mn[cur] + dist[nw][deep[cur]]); cur = cen[cur]; } return ret; } void Init(int N, int A[], int B[], int D[]) { n = N; for(int i = 0; i < n - 1; i++) { v[A[i]].pb({B[i],D[i]}); v[B[i]].pb({A[i],D[i]}); } memset(dist,0,sizeof(dist)); memset(cen,-1,sizeof(cen)); centroid_decomp(0, -2); return ; } long long Query(int S, int X[], int T, int Y[]) { long long ret = 1e18; for(int i = 0; i < n; i++) mn[i] = 1e18; for(int i = 0; i < S; i++) cen_upd(X[i]); for(int i = 0; i < T; i++) ret = min(ret,cen_query(Y[i])); return ret; } // int a[500005],b[500005],c[500005]; // int ps[500005],pt[500005]; // int main() // { // int n,q; // scanf("%d %d",&n,&q); // for(int i = 0; i < n - 1; i++) // { // scanf("%d %d %d",&a[i],&b[i],&c[i]); // } // Init(n, a, b, c); // for(int i = 0; i < q; i++) // { // int s,t; // scanf("%d %d",&s,&t); // for(int j = 0; j < s; j++) // scanf("%d",&ps[j]); // for(int j = 0; j < t; j++) // scanf("%d",&pt[j]); // printf("%lld\n",Query(s, ps, t, pt)); // } // return 0; // }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...