Submission #1182185

#TimeUsernameProblemLanguageResultExecution timeMemory
1182185PieArmyCat Exercise (JOI23_ho_t4)C++20
21 / 100
2096 ms62916 KiB
#include<bits/stdc++.h> typedef long long ll; #define pb push_back #define fr first #define sc second using namespace std; const int blok=450; int n; int val[200023],loc[200023]; vector<int>komsu[200023]; int dep[200023],eu[200023],son[200023]; int tim=0; int spar[400023][19],lg[400023]; int from[200023]; ll dp[200023]; int v[200023]; int bigger[200023]; int siz=0; void dfs(int pos){ spar[++tim][0]=pos; eu[pos]=tim; for(int x:komsu[pos]){ if(eu[x])continue; dep[x]=dep[pos]+1; dfs(x); spar[++tim][0]=pos; } son[pos]=tim; } int lca(int l,int r){ if(eu[l]>eu[r])swap(l,r); l=eu[l];r=eu[r]; int a=spar[l][lg[r-l+1]],b=spar[r-(1<<lg[r-l+1])+1][lg[r-l+1]]; if(dep[a]<dep[b])return a; return b; } int dis(int a,int b){ return dep[a]+dep[b]-2*dep[lca(a,b)]; } void dfs2(int pos,int m){ for(int x:komsu[pos]){ if(dep[x]<dep[pos])continue; bigger[x]=bigger[pos]+(val[pos]>=m); dfs2(x,m); } } void cal(){ int m=n+1; { int x=v[0]; while(x!=n+1){ m=min(val[x],m); x=v[x]; } } siz=0; v[0]=n+1; queue<int>q; for(int i=1;i<m;i++){ bigger[i]=0; from[loc[i]]=0; } for(int i=m;i<=n;i++){ q.push(loc[i]); while(q.size()){ int pos=q.front(); q.pop(); from[pos]=loc[i]; for(int x:komsu[pos]){ if(val[x]>=i||from[x])continue; q.push(x); } } } dfs2(1,m); } void ekle(int x){ siz++; for(int p=0;p!=n+1;p=v[p]){ if((p==0||eu[p]<eu[x])&&(v[p]==n+1||eu[v[p]]>eu[x])){ v[x]=v[p]; v[p]=x; return; } } } int main(){ ios_base::sync_with_stdio(false);cin.tie(NULL); cin>>n; for(int i=2;i<=n*2;i++){ lg[i]=lg[i/2]+1; } for(int i=1;i<=n;i++){ cin>>val[i]; loc[val[i]]=i; } for(int i=1;i<n;i++){ int x,y;cin>>x>>y; komsu[x].pb(y); komsu[y].pb(x); } dfs(1); for(int i=1;i<19;i++){ for(int j=1;j+(1<<i)-1<=tim;j++){ spar[j][i]=spar[j][i-1]; int x=spar[j+(1<<(i-1))][i-1]; if(dep[x]<dep[spar[j][i]])spar[j][i]=x; } } v[0]=n+1; ekle(loc[n]); ll ans=0; cal(); for(int i=n-1;i>=1;i--){ if(siz>=blok){ cal(); } int par=0; for(int p=v[0];p!=n+1;p=v[p]){ if(eu[loc[i]]>eu[p]&&eu[loc[i]]<=son[p]){ par=p; } } if(par!=0&&bigger[loc[i]]==bigger[par]){ from[loc[i]]=par; } int las=0; for(int p=v[par];p!=n+1;p=v[p]){ if(p==par){ las=0; continue; } if(par!=0&&eu[p]>son[par])break; if(las&&eu[p]<=son[las])continue; las=p; if(bigger[loc[i]]+bigger[p]==2*bigger[lca(loc[i],p)]){ if(val[p]<val[from[loc[i]]])from[loc[i]]=p; } } ekle(loc[i]); dp[loc[i]]=dp[from[loc[i]]]+dis(loc[i],from[loc[i]]); ans=max(ans,dp[loc[i]]); } cout<<ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...