Submission #1037424

#	Time	Username	Problem	Language	Result	Execution time	Memory
1037424		aaaaaarroz	Cat Exercise (JOI23_ho_t4)	C++17	100 / 100	274 ms	79280 KiB

Main

#include <bits/stdc++.h>
#define int long long
#define all(x) x.begin(),x.end()
#define ff first
#define ss second
#define pb push_back
using namespace std;
const int N=2e5+5;
int a[N],d[N],p[N],dp[N];
vector <int> g[N],g2[N];
int jmp[20][N];
void dfs(int v,int p){
  jmp[0][v]=p;
  for(auto to : g[v]){
    if(to!=p){
      d[to]=d[v]+1;
      dfs(to,v);
    }
  }
}
int lca(int v,int u){
  if(d[v]<d[u])swap(u,v);
  for(int k=19;k>=0;k--){
    if(d[jmp[k][v]]>=d[u]){
      v=jmp[k][v];
    }
  }
  if(u==v)return v;
  for(int k=19;k>=0;k--){
    if(jmp[k][v]!=jmp[k][u]){
      v=jmp[k][v];
      u=jmp[k][u];
    }
  }
  return jmp[0][v];
}
int find_set(int v){
  if(p[v]==v)return v;
  return p[v]=find_set(p[v]);
}
void union_set(int v,int u){
  u=find_set(u);
  p[u]=v;
  g2[v].pb(u);
}

int dist(int v,int u){
  int l=lca(u,v);
  return d[u]+d[v]-2*d[l];
}
void dfs2(int v,int p){
  for(auto to : g2[v]){
    if(to!=p){
      dfs2(to,v);
      dp[v]=max(dp[to]+dist(to,v),dp[v]);
    }
  }
}
signed main(){
  int n;
  cin>>n;
  for(int i=1;i<=n;i++){
    cin>>a[i];
    p[i]=i;
  }
  for(int i=0;i<n-1;i++){
    int u,v;
    cin>>u>>v;
    g[a[u]].pb(a[v]);
    g[a[v]].pb(a[u]);
  }
  dfs(n,n);
  for(int k=1;k<20;k++){
    for(int i=1;i<=n;i++){
      jmp[k][i]=jmp[k-1][jmp[k-1][i]];
    }
  }
  for(int i=2;i<=n;i++){
    for(auto to : g[i]){
      if(to<i){
        union_set(i,to);
      }
    }
  }
  dfs2(n,0);
  cout<<dp[n]<<"\n";
}

• Subtask 1: 7 / 7
• Subtask 2: 7 / 7
• Subtask 3: 7 / 7
• Subtask 4: 10 / 10
• Subtask 5: 20 / 20
• Subtask 6: 23 / 23
• Subtask 7: 26 / 26