Submission #963524

#	Time	Username	Problem	Language	Result	Execution time	Memory
963524		vladburac	Cat Exercise (JOI23_ho_t4)	C++17	100 / 100	313 ms	63828 KiB

Main

// credit: valeriu
#include <bits/stdc++.h>
using namespace std;
#define pii pair<long long, long long>
using ll = long long;
const int NMAX = 5e5;
const int VALMAX = 1e6;
const int LOGMAX = 18;
const int INF = 1e9;
const int MOD = 998244353;
mt19937 rnd( chrono::steady_clock::now().time_since_epoch().count() );

/*
#ifndef HOME
  ifstream fin( "regate.in" );
  ofstream fout( "regate.out" );
  #define cin fin
  #define cout fout
#endif // HOME
*/

vector <int> edges[NMAX+1];
pii h[NMAX+1];
int parent[NMAX+1];
int heavy[NMAX+1];

int find( int node ) {
  if( parent[node] == node )
    return node;
  return parent[node] = find( parent[node] );
}
void unite( int a, int b ) {
  a = find( a );
  b = find( b );
  if( a != b ) {
    parent[b] = a;
    heavy[a] = h[heavy[a]] > h[heavy[b]] ? heavy[a] : heavy[b];
  }
}

int anc[NMAX+1][LOGMAX+1];
int dep[NMAX+1];
void dfs( int node, int par = 0 ) {
  int i;
  anc[node][0] = par;
  dep[node] = dep[par] + 1;
  for( i = 1; i < LOGMAX; i++ ) {
    if( anc[node][i-1] != 0 )
      anc[node][i] = anc[anc[node][i-1]][i-1];
  }
  for( auto vec: edges[node] ) {
    if( vec != par )
      dfs( vec, node );
  }
}
int dist( int a, int b ) {
  int ca = a, cb = b, i;
  if( dep[a] < dep[b] )
    swap( a, b );
  int d = dep[a] - dep[b];
  for( i = 0; i < LOGMAX; i++ ) {
    if( d & ( 1 << i ) )
      a = anc[a][i];
  }
  for( i = LOGMAX - 1; i >= 0; i-- ) {
    if( anc[a][i] != anc[b][i] )
      a = anc[a][i], b = anc[b][i];
  }
  if( a != b )
    a = anc[a][0], b = anc[b][0];
  return dep[ca] - dep[a] + dep[cb] - dep[a];
}

ll dp[NMAX+1], ord[NMAX+1];
void solve() {
  int n, i, a, b, nxt;
  cin >> n;
  for( i = 1; i <= n; i++ ) {
    cin >> h[i].first, h[i].second = i;
    ord[i] = i;
  }
  for( i = 0; i < n - 1; i++ ) {
    cin >> a >> b;
    edges[a].push_back( b );
    edges[b].push_back( a );
  }
  sort( ord + 1, ord + n + 1, []( int a, int b ) {
      return h[a] < h[b];
  } );
  for( i = 1; i <= n; i++ )
    parent[i] = i, heavy[i] = i;
  dfs( 1 );
  //cout << dist( 3, 5 ) << "\n";
  for( i = 1; i <= n; i++ ) {
    for( auto vec: edges[ord[i]] ) {
      if( h[vec] < h[ord[i]] ) {
        nxt = heavy[find(vec)];
        dp[ord[i]] = max( dp[ord[i]], dp[nxt] + dist( nxt, ord[i] ) );
      }
    }
    for( auto vec: edges[ord[i]] ) {
      if( h[vec] < h[ord[i]] )
        unite( vec, ord[i] );
    }
  }
  cout << dp[ord[n]];
}
int main() {
  ios_base::sync_with_stdio( false );
  cin.tie( NULL );
  cout.tie( NULL );
  int t = 1;
  //cin >> t;
  while( t-- ) {
    solve();
  }
  return 0;
}

• 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