제출 #364910

#제출 시각아이디문제언어결과실행 시간메모리
364910ogibogi2004공장들 (JOI14_factories)C++14
33 / 100
8053 ms401484 KiB
#include "factories.h" #include <bits/stdc++.h> using namespace std; #define ll long long const ll INF=1e17; const int MAXN=2e6+6; const int lg=23; ll ans; vector<pair<int,ll> >g[MAXN]; vector<int>g1[MAXN]; int par[MAXN]; pair<int,int> dp[2*MAXN][lg]; int depth[MAXN]; ll depth1[MAXN]; int pw[2*MAXN],n; int wherel[MAXN],wherer[MAXN]; vector<int>dfs_order; int st[MAXN]; bool f[MAXN]; ll mind[MAXN]; void dfs1(int u,int p) { dfs_order.push_back(u); for(auto v:g[u]) { if(v.first==p)continue; depth1[v.first]=depth1[u]+v.second; depth[v.first]=depth[u]+1; dfs1(v.first,u); dfs_order.push_back(u); } } void precompute() { int t=1,c=0; for(int i=1;i<=MAXN;i++) { if(t*2<=i) { t*=2;c++; } pw[i]=c; } for(int i=0;i<dfs_order.size();i++) { dp[i][0]={depth[dfs_order[i]],dfs_order[i]}; } for(int i=0;i<dfs_order.size();i++) { wherer[dfs_order[i]]=i; } for(int i=dfs_order.size()-1;i>=0;i--) { wherel[dfs_order[i]]=i; } for(int step=1;step<lg;step++) { for(int i=0;i<dfs_order.size();i++) { dp[i][step]=dp[i][step-1]; if(i+(1<<(step-1))<dfs_order.size()) { dp[i][step]=min(dp[i][step],dp[i+(1<<(step-1))][step-1]); } } } } int lca(int x,int y) { if(wherel[x]>wherel[y])swap(x,y); int i1=wherel[x]; int i2=wherer[y]; int d=i2-i1+1; int t=pw[d]; pair<int,int>ret=dp[i1][t]; ret=min(ret,dp[i2-(1<<t)+1][t]); return ret.second; } ll dist(int x,int y) { return depth1[x]+depth1[y]-2*depth1[lca(x,y)]; } void dfs2(int u,int p) { st[u]=1; for(auto v:g[u]) { if(v.first==p)continue; if(f[v.first])continue; dfs2(v.first,u); st[u]+=st[v.first]; } } int find(int u,int p,int t) { for(auto v:g[u]) { if(v.first==p)continue; if(f[v.first])continue; if(st[v.first]>t/2)return find(v.first,u,t); } return u; } void decompose(int u,int p) { dfs2(u,p); int c=find(u,p,st[u]); if(p>0) { g1[p].push_back(c); } par[c]=p; f[c]=1; for(auto v:g[c]) { if(f[v.first])continue; decompose(v.first,c); } } void Init(int N, int A[], int B[], int D[]) { n=N; for(int i=0;i<n-1;i++) { g[A[i]+1].push_back({B[i]+1,D[i]}); g[B[i]+1].push_back({A[i]+1,D[i]}); } dfs1(1,0); precompute(); decompose(1,-1); for(int i=0;i<MAXN;i++)mind[i]=INF; } void update(int x) { mind[x]=0; int y=par[x]; while(y>0) { mind[y]=min(mind[y],dist(x,y)); y=par[y]; } } void clear(int x) { mind[x]=INF; int y=par[x]; while(y>0) { mind[y]=INF; y=par[y]; } } void check(int x) { ans=min(ans,mind[x]); int y=par[x]; while(y>0) { ans=min(ans,mind[y]+dist(x,y)); y=par[y]; } } long long Query(int S, int X[], int T, int Y[]) { ans=INF; for(int i=0;i<S;i++) { update(X[i]+1); } for(int i=0;i<T;i++) { check(Y[i]+1); } for(int i=0;i<S;i++) { clear(X[i]+1); } return ans; }

컴파일 시 표준 에러 (stderr) 메시지

factories.cpp: In function 'void precompute()':
factories.cpp:44:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |  for(int i=0;i<dfs_order.size();i++)
      |              ~^~~~~~~~~~~~~~~~~
factories.cpp:48:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |  for(int i=0;i<dfs_order.size();i++)
      |              ~^~~~~~~~~~~~~~~~~
factories.cpp:59:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |   for(int i=0;i<dfs_order.size();i++)
      |               ~^~~~~~~~~~~~~~~~~
factories.cpp:62:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |    if(i+(1<<(step-1))<dfs_order.size())
      |       ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...