Submission #13563

#TimeUsernameProblemLanguageResultExecution timeMemory
13563dohyun0324Factories (JOI14_factories)C++98
0 / 100
4503 ms161648 KiB
#include "factories.h" #include<vector> #include<algorithm> #include<string.h> using namespace std; typedef pair<int,int> ppair; ppair lev[500010]; int r,s,cnt,ch[500010],n,q,go[500010],num[500010],x,y,z,top[500010],len[500010]; long long dap=2147483647; vector<int>con[500010]; vector<int>cost[500010]; vector<int>treeb[500010]; vector<int>trees[500010]; struct data{ int p,q,len; }ch2[500010]; struct data2{ int x,cost; }anc[500010]; void dfs(int x,int l) { int i; ch[x]=1; lev[x].first=l; lev[x].second=x; for(i=0;i<con[x].size();i++){ if(ch[con[x][i]]) continue; anc[con[x][i]].x=x; anc[con[x][i]].cost=cost[x][i]; dfs(con[x][i],l+1); num[x]+=num[con[x][i]]; } num[x]++; } void dfs2(int x) { int i,maxi=-2147483647,p=-1; ch2[x].p=cnt; top[cnt]++; ch2[x].q=top[cnt]; go[x]=s; for(i=0;i<con[x].size();i++){ if(ch2[con[x][i]].p==0 && maxi<num[con[x][i]]) maxi=num[con[x][i]], p=i; } if(p==-1) return; ch2[con[x][p]].len=ch2[x].len+cost[x][p]; len[cnt]=ch2[x].len+cost[x][p]; dfs2(con[x][p]); } void Init(int n, int A[], int B[], int D[]) { int i,j,t,c; for(i=0;i<n-1;i++){ x=A[i]+1; y=B[i]+1; z=D[i]; con[x].push_back(y); con[y].push_back(x); cost[x].push_back(z); cost[y].push_back(z); } dfs(1,1); sort(lev+1,lev+n+1); for(i=1;i<=n;i++){ t=lev[i].second; if(!ch2[t].p){cnt++; s=t; dfs2(t);} } for(i=1;i<=cnt;i++){ for(c=1;c<=top[i];c*=2); top[i]=c; } for(i=1;i<=cnt;i++){ for(j=0;j<=top[i]*2;j++){treeb[i].push_back(2147483647); trees[i].push_back(2147483647);} } } void updateb(int p,int x,int val) { x+=top[p]-1; treeb[p][x]=val; x/=2; while(x){ treeb[p][x]=min(treeb[p][x*2],treeb[p][x*2+1]); x/=2; } } void updates(int p,int x,int val) { x+=top[p]-1; trees[p][x]=val; x/=2; while(x){ trees[p][x]=min(trees[p][x*2],trees[p][x*2+1]); x/=2; } } void pro1(int x,int sw) { int sum=0,p,q; while(x){ p=ch2[x].p; q=ch2[x].q; if(sw==0){ updateb(p,q,sum+len[p]-ch2[x].len); updates(p,q,sum-len[p]+ch2[x].len); } else{ updateb(p,q,2147483647); updates(p,q,2147483647); } sum+=ch2[x].len+anc[go[x]].cost; x=anc[go[x]].x; } } int queryb(int p,int x,int y,int k,int s,int e) { if(x>e || y<s) return 2147483647; if(s<=x && y<=e) return treeb[p][k]; return min(queryb(p,x,(x+y)/2,k*2,s,e),queryb(p,(x+y)/2+1,y,k*2+1,s,e)); } int querys(int p,int x,int y,int k,int s,int e) { if(x>e || y<s) return 2147483647; if(s<=x && y<=e) return trees[p][k]; return min(querys(p,x,(x+y)/2,k*2,s,e),querys(p,(x+y)/2+1,y,k*2+1,s,e)); } void pro2(int x) { int sum=0,p,q; while(x){ p=ch2[x].p; q=ch2[x].q; dap=min(dap,(long long)sum-len[p]+ch2[x].len+queryb(p,1,top[p],1,1,q)); dap=min(dap,(long long)sum+len[p]-ch2[x].len+querys(p,1,top[p],1,q,top[p])); sum+=ch2[x].len+anc[go[x]].cost; x=anc[go[x]].x; } } long long Query(int S, int X[], int T, int Y[]) { int i,j; dap=2147483647; for(i=0;i<S;i++) pro1(X[i]+1,0); for(i=0;i<T;i++) pro2(Y[i]+1); for(i=0;i<S;i++) pro1(X[i]+1,1); return dap; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...