Submission #1195317

#TimeUsernameProblemLanguageResultExecution timeMemory
1195317NewtonabcCat Exercise (JOI23_ho_t4)C++20
54 / 100
198 ms43560 KiB
#include<bits/stdc++.h> using namespace std; const int N=2e5+10; int p[N],pa[N],dp[N][20],d[N],dpb[N]; vector<int> adj[N]; bool cp(int a,int b){ return p[a]<p[b]; } void dfs(int u,int p){ for(auto v:adj[u]){ if(v==p) continue; dp[v][0]=u; d[v]=d[u]+1; dfs(v,u); } } int lca(int a,int b){ //make same depth (put b up) if(d[b]<d[a]) swap(a,b); for(int i=19;i>=0;i--) if(d[dp[b][i]]>=d[a]) b=dp[b][i]; if(a==b) return a; for(int i=19;i>=0;i--) if(dp[b][i]!=dp[a][i]) a=dp[a][i],b=dp[b][i]; return dp[a][0]; } int path(int a,int b){ return d[a]+d[b]-2*d[lca(a,b)]; } int root(int x){ if(pa[x]==x) return x; return pa[x]=root(pa[x]); } void merge(int a,int b){ int ra=root(a),rb=root(b); if(ra==rb) return; //root is the node that has maximum height if(p[ra]>p[rb]) pa[rb]=ra; else pa[ra]=rb; } int main(){ int n; cin>>n; for(int i=1;i<=n;i++) cin>>p[i]; for(int i=1;i<=n;i++) pa[i]=i; for(int i=0;i<n-1;i++){ int u,v; cin>>u >>v; adj[u].push_back(v); adj[v].push_back(u); } vector<int> sp; for(int i=1;i<=n;i++) sp.push_back(i); sort(sp.begin(),sp.end(),cp); dfs(sp.back(),-1); dp[sp.back()][0]=sp.back(); for(int i=1;i<20;i++) for(int j=1;j<=n;j++) dp[j][i]=dp[dp[j][i-1]][i-1]; for(auto u:sp){ for(auto v:adj[u]){ if(p[v]>p[u]) continue; //cout<<u <<" " <<v <<" " <<dpb[u] <<" " <<dpb[v]+path(u,root(v)) <<"\n"; //cout<<root(u) <<" " <<root(v) <<"\n"; dpb[u]=max(dpb[u],dpb[root(v)]+path(u,root(v))); merge(u,v); //cout<<root(u) <<" " <<root(v) <<"\n"; } } cout<<dpb[sp.back()]; }
#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...