제출 #1128500

#제출 시각아이디문제언어결과실행 시간메모리
1128500Nonoze공장들 (JOI14_factories)C++20
33 / 100
8103 ms225664 KiB
#include "factories.h" #include <bits/stdc++.h> using namespace std; #define int long long #define fi first #define se second #define cmin(a, b) a = min(a, b) const int inf = 1e18; const signed LOG=18; signed n; vector<pair<signed, signed>> adj[500005]; pair<signed, int> up[500005][LOG]; signed depth[500005]; void dfsinit(signed u, signed p) { for (auto [v, w]: adj[u]) if (v!=p) { up[v][0]={u, w}; for (int i=1; i<LOG; i++) { if (up[v][i-1].fi==-1) break; up[v][i]=up[up[v][i-1].fi][i-1]; up[v][i].se+=up[v][i-1].se; } depth[v]=depth[u]+1; dfsinit(v, u); } } int dist(signed a, signed b) { if (a==b) return 0; if (depth[a]<depth[b]) swap(a, b); int ans=0; signed k=depth[a]-depth[b]; for (signed i=0; i<LOG&&k; i++) { if (k&(1<<i)) ans+=up[a][i].se, a=up[a][i].fi, k^=1<<i; } if (a==b) return ans; for (signed i=LOG-1; i>=0; i--) if (up[a][i].fi!=up[b][i].fi) { ans+=up[a][i].se+up[b][i].se; a=up[a][i].fi, b=up[b][i].fi; } return ans+up[a][0].se+up[b][0].se; } signed sz[500005], par[500005]; bool centro[500005]; void dfs(signed u, signed p) { sz[u]=1; for (auto [v, w]: adj[u]) if (v!=p && !centro[v]) { dfs(v, u); sz[u]+=sz[v]; } } signed centroid(signed u, signed p, signed obj) { for (auto [v, w]: adj[u]) if (v!=p && !centro[v]) { if (sz[v]*2>=obj) return centroid(v, u, obj); } return u; } signed decompose(signed u, signed p) { if (centro[u]) return u; dfs(u, u); signed c=centroid(u, u, sz[u]); centro[c]=1; par[c]=p; for (auto [v, w]: adj[c]) if (!centro[v]) { decompose(v, c); } return c; } int distres[500005]; void Init(signed N, signed A[], signed B[], signed D[]) { n=N; for (int i=0; i<n-1; i++) { adj[A[i]].push_back({B[i], D[i]}); adj[B[i]].push_back({A[i], D[i]}); distres[i]=inf, centro[i]=0; } distres[n-1]=inf, centro[n-1]=0; dfsinit(0, 0); decompose(0, -1); } int Query(signed S, signed X[], signed T, signed Y[]) { int ans=inf; for (int i=0; i<S; i++) { int act=X[i]; while (act!=-1) { cmin(distres[act], dist(act, X[i])); act=par[act]; } } for (int i=0; i<T; i++) { int act=Y[i]; while (act!=-1) { cmin(ans, distres[act]+dist(act, Y[i])); act=par[act]; } } for (int i=0; i<S; i++) { int act=X[i]; while (act!=-1) { distres[act]=inf; act=par[act]; } } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...