제출 #409468

#제출 시각아이디문제언어결과실행 시간메모리
409468ScarletS공장들 (JOI14_factories)C++17
33 / 100
8000 ms127352 KiB
#pragma GCC optimize("Ofast,unroll-loops") #pragma GCC target("avx,avx2,sse,sse2") #include <bits/stdc++.h> #define ll long long #define sz(x) (int)(x).size() using namespace std; const int N = 5e5+4, lg = 19; const ll INF = 1e18; int pt[N], sub[N], up[lg][N], tin[N], tout[N], ct; ll h[N], ans[N]; vector<array<int,2>> e[N]; bitset<N> b; bool isAncestor(int x, int y) { return (tin[x]<=tin[y]&&tout[y]<=tout[x]); } int lca(int x, int y) { if (isAncestor(x,y)) return x; if (isAncestor(y,x)) return y; for (int i=lg-1;i>=0;--i) if (!isAncestor(up[i][x],y)) x=up[i][x]; return up[0][x]; } ll dist(int x, int y) { int z = lca(x,y); return h[x]+h[y]-h[z]*2; } void lcaDfs(int c, int p, ll x) { tin[c]=++ct; h[c]=x; up[0][c]=p; for (int i=1;i<lg;++i) up[i][c]=up[i-1][up[i-1][c]]; for (auto i : e[c]) if (i[0]!=p) lcaDfs(i[0],c,x+i[1]); tout[c]=++ct; } void subDfs(int c, int p) { sub[c]=1; for (auto i : e[c]) if (i[0]!=p&&!b[i[0]]) { subDfs(i[0],c); sub[c]+=sub[i[0]]; } } void centDfs(int c, int p, int t) { int mx=t-sub[c]; for (auto i : e[c]) if (i[0]!=p&&!b[i[0]]) { centDfs(i[0],c,t); mx=max(mx,sub[i[0]]); } if (mx<=t/2) ct=c; } void solve(int r, int p) { subDfs(r,0); centDfs(r,0,sub[r]); int X = ct; pt[X]=p; b[X]=1; for (auto i : e[X]) if (!b[i[0]]) solve(i[0],X); } void Init(int n, int A[], int B[], int w[]) { for (int i=0;i<n-1;++i) { ans[i+1]=INF; e[++A[i]].push_back({++B[i],w[i]}); e[B[i]].push_back({A[i],w[i]}); } ans[n]=INF; lcaDfs(1,0,0); tout[0]=++ct; solve(1,0); } ll Query(int s, int x[], int t, int y[]) { for (int i=0;i<s;++i) { ++x[i]; for (int j=x[i];j!=0;j=pt[j]) ans[j]=min(ans[j],dist(x[i],j)); } ll ret = INF; for (int i=0;i<t;++i) { ++y[i]; for (int j=y[i];j!=0;j=pt[j]) ret=min(ret,ans[j]+dist(y[i],j)); } for (int i=0;i<s;++i) for (int j=x[i];j!=0;j=pt[j]) ans[j]=INF; return ret; } // int main() // { // ios_base::sync_with_stdio(0); cin.tie(0); // int n,q,s,t; // cin>>n>>q; // int a[n-1],b[n-1],c[n-1]; // for (int i=0;i<n-1;++i) // cin>>a[i]>>b[i]>>c[i]; // Init(n,a,b,c); // while (q--) // { // cin>>s>>t; // int x[s],y[t]; // for (int i=0;i<s;++i) // cin>>x[i]; // for (int i=0;i<t;++i) // cin>>y[i]; // 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...