Submission #545054

#	Time	Username	Problem	Language	Result	Execution time	Memory
545054		chonka	Mergers (JOI19_mergers)	C++98	100 / 100	1287 ms	139420 KiB

mergers

#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;

// mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

#define MAXN 500007
#define LOG 20

int n , k ;
vector < int > v[ MAXN ] ;
int a[ MAXN ] ;
int lvl[ MAXN ] ;
int LCA[ MAXN ][ LOG ] ;
int st[ MAXN ] , tp ;
vector < int > col[ MAXN ] ;

void init ( int vertex , int prv ) {
    st[ vertex ] = ++ tp ;
    for ( int i = 1 ; i < LOG ; ++ i ) {
        LCA[ vertex ][ i ] = LCA[ LCA[ vertex ][ i - 1 ] ][ i - 1 ] ;
    }
    for ( auto x : v[ vertex ] ) {
        if ( x == prv ) { continue ; }
        lvl[ x ] = lvl[ vertex ] + 1 ;
        LCA[ x ][ 0 ] = vertex ;
        init ( x , vertex ) ;
    }
}

int ori[ MAXN ] ;

int get_lca ( int x , int y ) {
    for ( int i = LOG - 1 ; i >= 0 ; -- i ) {
        if ( lvl[ x ] - ( 1 << i ) >= lvl[ y ] ) {
            x = LCA[ x ][ i ] ;
        }
        if ( lvl[ y ] - ( 1 << i ) >= lvl[ x ] ) {
            y = LCA[ y ][ i ] ;
        }
    }
    for ( int i = LOG - 1 ; i >= 0 ; -- i ) {
        if ( LCA[ x ][ i ] != LCA[ y ][ i ] ) {
            x = LCA[ x ][ i ] ;
            y = LCA[ y ][ i ] ;
        }
    }
    if ( x != y ) { x = LCA[ x ][ 0 ] ; }
    return x ;
}

int prv[ MAXN ] , rnk[ MAXN ] ;
int hh[ MAXN ] ;

int get ( int x ) {
    if ( prv[ x ] == -1 ) { return x ; }
    int y = get ( prv[ x ] ) ;
    prv[ x ] = y ;
    return y ;
}
void unite ( int x , int y ) {
    int k1 = get ( x ) , k2 = get ( y ) ;
    if ( k1 != k2 ) {
        if ( rnk[ k1 ] >= rnk[ k2 ] ) {
            rnk[ k1 ] += ( rnk[ k1 ] == rnk[ k2 ] ) ;
            prv[ k2 ] = k1 ;
        }
        else {
            prv[ k1 ] = k2 ;
        }
    }
}

int dfs ( int vertex , int prv ) {
    int ret = lvl[ ori[ a[ vertex ] ] ] ;
    for ( auto x : v[ vertex ] ) {
        if ( x == prv ) { continue ; }
        int aux = dfs ( x , vertex ) ;
        ret = min ( ret , aux ) ;
    }
    if ( vertex == 1 ) { return ret ; }
    if ( ret < lvl[ vertex ] ) {
        unite ( vertex , prv ) ;
    }
    return ret ;
}

void input ( ) {
    cin >> n >> k ;
    for ( int i = 1 ; i < n ; ++ i ) {
        int x , y ;
        cin >> x >> y ;
        v[ x ].push_back ( y ) ;
        v[ y ].push_back ( x ) ;
    }
    for ( int i = 1 ; i <= n ; ++ i ) {
        cin >> a[ i ] ;
        col[ a[ i ] ].push_back ( i ) ;
    }
}

void solve ( ) {
    init ( 1 , -1 ) ;
    auto cmp = [ & ] ( int x , int y ) {
        return ( st[ x ] < st[ y ] ) ;
    };
    for ( int i = 1 ; i <= k ; ++ i ) {
        sort ( col[ i ].begin ( ) , col[ i ].end ( ) , cmp ) ;
        ori[ i ] = get_lca ( col[ i ].front ( ) , col[ i ].back ( ) ) ;
    }
    for ( int i = 1 ; i <= n ; ++ i ) {
        prv[ i ] = -1 ;
    }
    dfs ( 1 , -1 ) ;
    for ( int i = 1 ; i <= n ; ++ i ) {
        for ( auto j : v[ i ] ) {
            if ( get ( i ) != get ( j ) ) {
                ++ hh[ get ( i ) ] ;
            }
        }
    }
    int ans = 0 ;
    for ( int i = 1 ; i <= n ; ++ i ) {
        if ( get ( i ) == i && hh[ i ] == 1 ) {
            ++ ans ;
        }
    }
    cout << ( ans + 1 ) / 2 << "\n" ;
}

int main ( ) {
    ios_base :: sync_with_stdio ( false ) ;
    cin.tie ( NULL ) ;
    int t = 1 ;
    // cin >> t ;
    while ( t -- ) {
        input ( ) ;
        solve ( ) ;
    }
    return 0 ;
}

• Subtask 1: 10 / 10
• Subtask 2: 24 / 24
• Subtask 3: 14 / 14
• Subtask 4: 22 / 22
• Subtask 5: 30 / 30