Submission #767150

#	Time	Username	Problem	Language	Result	Execution time	Memory
767150		lollipop	Cat Exercise (JOI23_ho_t4)	C++17	100 / 100	341 ms	77008 KiB

Main

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
#define int long long
#define pb push_back
#define s second
#define f first
#define pf push_front
#define inf 100000000000000000
#define bitebi __builtin_popcountll
#define FOR( i , n ) for( int i = 0 ; i < n ; i ++ )
#define YES cout <<"YES\n"
#define NO cout << "NO\n"
#define debug cout << "Here Fine" << endl ;
#define pr pair < int , int >
#define fbo find_by_order // returns iterator
#define ook order_of_key // returns strictly less numbers than key
using namespace std ;
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
const double Pi=acos(-1.0);
const double EPS=1E-8;
const int mod =  1000000007 ;
const int mod1 = 998244353 ;
const int N = 2e5 + 10 ;
mt19937 R(time(0));
map < int , int > ma , ma1 ;
int node[ 4 * N ] , w[ N ] , inv[ N ] , ap[ N ] ;
void build( int v , int vl , int vr ){
	 if( vl == vr ){
	 	node[ v ] = ap[ vl ] ;
	 	return ;
	 }
	 int vm = ( vl + vr ) / 2 ;
	 build( v + v , vl , vm ) ;
	 build( v + v + 1 , vm + 1 , vr ) ;
	 node[ v ] = max( node[ v + v ] , node[ v + v + 1 ] ) ;
	 return ;
}
void update( int v , int vl , int vr , int pos ){
	 if( vl == vr ){
	 	node[ v ] = - 1 ;
	 	return ; 
	 }
	 int vm = ( vl + vr ) / 2 ;
	 if( vm >= pos ) update( v + v , vl , vm , pos ) ;
	 else update( v + v + 1 , vm + 1 , vr , pos ) ;
	 node[ v ] = max( node[ v + v ] , node[ v + v + 1 ] ) ; 
	 return ;
}
int get( int v , int vl , int vr , int l , int r ){
	if( l > r ) return -1 ;
	if( vl == l && vr == r ) return node[ v ] ;
	int vm = ( vl + vr ) / 2 ;
	int a = get( v + v , vl , vm , l , min( r , vm ) ) ;
	int b = get( v + v + 1 , vm + 1 , vr , max( vm + 1 , l ) , r ) ;
	return max( a , b ) ;
}
vector < int > v[ N ] ;
int h[ N ] , tin[ N ] , tout[ N ] , timer = 1 ; 
int pp[ N ][ 20 ] , xx[ 20 ] , n ; 
void dfs( int node , int parent , int hh ){
	 ap[ timer ] = w[ node ] ;
	 tin[ node ] = timer ; 
	 h[ node ] = hh ;
	 timer ++ ; 
	 pp[ node ][ 0 ] = parent ;
	 for( int j = 1 ; j < 20 ; j ++ ){
	 	if( hh - xx[ j ] < 0 ) pp[ node ][ j ] = -1 ;
	 	else pp[ node ][ j ] = pp[ pp[ node ][ j - 1 ] ][ j - 1 ] ; 
	 }
	 for( auto x : v[ node ] ){
	 	if( x == parent ) continue ;
	 	dfs( x , node , hh + 1 ) ; 
	 }
	 tout[ node ] = timer - 1 ; 
}
bool is_lca( int a , int b ){
	if( a == -1 ) return true ; 
	if( a == b ) return true ;
	if( tin[ a ] <= tin[ b ] && tout[ a ] >= tout[ b ] ) return true ;
	return false ; 
}
int find_lca( int a , int b ){
	if( is_lca( a , b ) == true ) return a ;
	if( is_lca( b , a ) == true ) return b ;
	for( int j = 19 ; j >= 0 ; j -- ){
		if( is_lca( pp[ a ][ j ] , b ) == false ) a = pp[ a ][ j ] ; 
	}
	return pp[ a ][ 0 ] ; 
}
int dist( int a , int b ){
	if( a == -1 || b == -1 ) return 0 ;
	int c = find_lca( a , b ) ;
	int ans = abs( h[ c ] - h[ a ] ) + abs( h[ c ] - h[ b ] ) ;
	return ans ; 
}
int been[ N ] ; 
int sol( int st , int frm , int papi ){
//	cout << st << " " << frm << " " << papi << " tur " ; 
	int alr = dist( st , frm ) ;
//	cout << alr << endl ; 
	been[ st ] = 1 ;
	update( 1 , 1 , n , tin[ st ] ) ; 
	int ans = alr ; 
	for( auto x : v[ st ] ){
		if( h[ x ] < h[ st ] ) continue ; 
		if( been[ x ] == 1 ) continue ; 
		int mx = get( 1 , 1 , n , tin[ x ] , tout[ x ] ) ; 
		if( mx == -1 ) continue ; 
		mx = inv[ mx ] ;
		ans = max( ans , sol( mx , st , x ) + alr ) ; 
	}
   if( papi != -1 ){
	int x = papi ; 
	int mx = get( 1 , 1 , n , tin[ x ] , tout[ x ] ) ;
	if( mx != -1 ){
        mx = inv[ mx ] ; 
    	ans = max( ans , sol( mx , st , x ) + alr ) ;
    }
   }
	return ans ; 
}
void solve(){
     cin >> n ;
     FOR( i , n ){
     	cin >> w[ i + 1 ] ;
     	inv[ w[ i + 1 ] ] = i + 1 ; 
	 }
     FOR( i , n - 1 ){
     	int x , y ; cin >> x >> y ;
     	v[ x ].pb( y ) ; v[ y ].pb( x ) ; 
	 }
     dfs( inv[ n ] , -1 , 0 ) ; 
     build( 1 , 1 , n ) ; 
     int ans = sol( inv[ n ] , -1 , -1 ) ; 
     cout << ans ; 
}
signed main() {
   ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
   xx[ 0 ] = 1 ; 
   for( int j = 1 ; j < 20 ; j ++ ) xx[ j ] = xx[ j - 1 ] * 2 ; 
   int t = 1 ; // cin >> t ;
   while( t -- ){
   	 solve() ;
   }

}

• 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