Submission #1272916

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272916		meisgood	Cat Exercise (JOI23_ho_t4)	C++20	0 / 100	2 ms	576 KiB

Main

#include <bits/stdc++.h>
using namespace std ;
#define int long long
int A[200003] ;
vector <int> adj[200003] ;
int gp[200003] ;
int dp[200003] ;
int mxd[200003] ;
int anc[33][200003] ;
int dsu(int x){
  if (x==gp[x]) return x ;
  gp[x]=dsu(gp[x]) ;
  return gp[x] ;
}
int dep[200003] ;
void dfs(int x,int par){
  for (auto a : adj[x]) if (a!=par) dep[a]=dep[x]+1,anc[0][a]=x,dfs(a,x) ;
}
int lca(int a,int b){
  if (dep[a]<dep[b]) swap(a,b) ;
  for (int i = 25 ; i >= 0 ; i --){
    if (dep[anc[i][a]]>=dep[b]) a=anc[i][a] ;
  }
  if (a==b) return a ;
  for (int i = 25 ; i >= 0 ; i --){
    if (anc[i][a]!=anc[i][b]) a=anc[i][a],b=anc[i][b] ;
  }
  return anc[0][a] ;
}
signed main(){
  int N,i,j ;
  cin >> N ;
  for (i = 1 ; i <= N ; i ++) gp[i]=i,dp[i]=0,mxd[i]=i ;
  for (i = 1 ; i <= N ; i ++) cin >> A[i] ;
  for (i = 0 ; i < N-1 ; i ++){
    int a,b ;
    cin >> a >> b ;
    adj[A[a]].push_back(A[b]) ;
    adj[A[b]].push_back(A[a]) ;
  }
  anc[0][N]=N ;
  dfs(N,-1) ;
  for (int k = 1 ; k <= 25 ; k ++){
    for (i = 1 ; i <= N ; i ++) anc[k][i]=anc[k-1][anc[k-1][i]] ;
  }
  for (i = 1 ; i <= N ; i ++){
    bool ok=0 ;
    for (auto a : adj[i]){
      if (dep[a]>dep[i]&&a<i){
        ok=1 ;
        int mx=0 ;
        for (auto b : adj[a]){
          if (dep[b]>dep[a]&&b<i){
            mx=max(mx,dp[b]) ;
          }
        }
        dp[i]+=mx ;
      }
    }
    // if (ok) dp[i]++ ;
    // int rt=i ;
    // for (auto a : adj[i]){
    //   if (a>i) continue ;
    //   if (dep[a]>dep[i]) ;
    //   else rt=dsu(a) ;
    // }
    for (auto a : adj[i]){
      if (a>i) continue ;
      if (dep[a]>dep[i]){
        gp[a]=dsu(i) ;
        dp[i]=max(dp[i],dp[a]+1) ;
        mxd[dsu(i)]=max(mxd[dsu(i)],mxd[a]) ;
      }
    }
    dp[dsu(i)]=max(dp[dsu(i)],dp[i]) ;
    // cout << i << " " << dsu(i) << " " << dp[dsu(i)] << endl ;
    for (auto a : adj[i]){
      if (a>i) continue ;
      if (dep[a]>dep[i]) ;
      else {
        gp[i]=dsu(a) ;
        dp[dsu(a)]+=(dep[mxd[i]]+dep[mxd[dsu(a)]]-2*dep[lca(mxd[i],mxd[dsu(a)])]) ;
        // cout << mxd[i] << " " << mxd[dsu(a)] << " " << lca(mxd[i],mxd[dsu(a)]) << endl ;
        // cout << (dep[mxd[i]]+dep[mxd[dsu(a)]]-2*dep[lca(mxd[i],mxd[dsu(a)])])*2 << endl ;
        mxd[dsu(a)]=max(mxd[dsu(a)],mxd[i]) ;
      }
    }
    // cout << i << " " << dsu(i) << " " << dp[dsu(i)] << endl ;
    dp[dsu(i)]+=dep[i]-dep[dsu(i)] ;
    // cout << i << " " << dsu(i) << " " << dp[dsu(i)] << endl ;
  }
  cout << dp[N] << endl ;
  return 0 ;
}

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