Submission #1182051

#TimeUsernameProblemLanguageResultExecution timeMemory
1182051PieArmyCat Exercise (JOI23_ho_t4)C++20
21 / 100
2095 ms61720 KiB
#include<bits/stdc++.h> typedef long long ll; #define pb push_back #define fr first #define sc second using namespace std; 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]; vector<int>v; int bigger[200023]; 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 query(int l,int 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 lca(int a,int b){ if(eu[a]>eu[b])swap(a,b); return query(eu[a],eu[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[x]>=m); dfs2(x,m); } } void cal(){ int m=val[v[0]]; for(int x:v){ m=min(val[x],m); } v.clear(); queue<int>q; for(int i=1;i<m;i++){ from[loc[i]]=0; bigger[i]=0; } for(int i=m;i<=n;i++){ q.push(loc[i]); while(q.size()){ int pos=q.front(); q.pop(); if(loc[i]!=pos)from[pos]=loc[i]; for(int x:komsu[pos]){ if(val[x]>=i)continue; if(from[x])continue; q.push(x); } } } bigger[1]=(val[1]>=m); dfs2(1,m); } 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.pb(loc[n]); ll ans=0; cal(); for(int i=n-1;i>=1;i--){ if(int(v.size())*int(v.size())>=n){ cal(); } sort(v.begin(),v.end(),[&](const int &x,const int &y){ return eu[x]<eu[y]; }); int par=-1; for(int j=0;j<v.size();j++){ if(lca(v[j],loc[i])==v[j]){ par=j; } } if(par!=-1&&bigger[loc[i]]==bigger[v[par]]){ from[loc[i]]=v[par]; } int las=0; for(int j=par+1;j<v.size();j++){ if(par!=-1&&eu[v[j]]>son[v[par]])break; if(las&&eu[v[j]]<=son[las])continue; las=v[j]; if(bigger[loc[i]]+bigger[v[j]]==2*bigger[lca(loc[i],v[j])]){ if(val[v[j]]<val[from[loc[i]]])from[loc[i]]=v[j]; } } v.pb(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...