Submission #540926

#	Time	Username	Problem	Language	Result	Execution time	Memory
540926		chonka	Meetings 2 (JOI21_meetings2)	C++98	0 / 100	3 ms	5076 KiB

meetings2

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

#define MAXN 200007
#define LOG 20

int n ;
vector < int > v[ MAXN ] ;
int comp[ MAXN ] , lvl[ MAXN ] ;
int LCA[ MAXN ][ LOG + 1 ] ;
int st[ MAXN ] , en[ MAXN ] ;
int tp ;
int used[ MAXN ] ;

int total ;
int subtree[ MAXN ] , d[ MAXN ] ;
int ans[ MAXN ] ;
int mxseen[ MAXN ] ;

void from_root ( int vertex , int prv ) {
    st[ vertex ] = ++ tp ;
    comp[ vertex ] = 1 ;
    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 ; 
        from_root ( x , vertex ) ;
        comp[ vertex ] += comp[ x ] ;
    }
    en[ vertex ] = tp ;
}

void init ( int vertex , int prv ) {
    ++ total ;
    subtree[ vertex ] = 1 ;
    for ( auto x : v[ vertex ] ) {
        if ( used[ x ] == 1 || x == prv ) { continue ; }
        d[ x ] = d[ vertex ] + 1 ;
        init ( x , vertex ) ;
        subtree[ vertex ] += subtree[ x ] ;
    }
}

int get_cen ( int vertex , int prv ) {
    for ( auto x : v[ vertex ] ) {
        if ( used[ x ] == 1 || x == prv ) { continue ; }
        if ( 2 * subtree[ x ] > total ) {
            return get_cen ( x , vertex ) ;
        }
    }
    return vertex ;
}

int suff[ MAXN ] ;
int mx_cur[ MAXN ] ;

class Tree {
public :
    int tr[ 4 * MAXN ] ;
    void init ( int where , int IL , int IR ) {
        tr[ where ] = -MAXN ;
        if ( IL == IR ) { return ; }
        int mid = ( IL + IR ) / 2 ;
        init ( 2 * where , IL , mid ) ;
        init ( 2 * where + 1 , mid + 1 , IR ) ;
    }
    void update ( int where , int IL , int IR , int pos , int nw ) {
        if ( IL == IR ) {
            if ( nw < 0 ) { tr[ where ] = -MAXN ; }
            else { tr[ where ] = max ( tr[ where ] , nw ) ; }
            return ;
        }
        int mid = ( IL + IR ) / 2 ;
        if ( pos <= mid ) {
            update ( 2 * where , IL , mid , pos , nw ) ;
        }
        else {
            update ( 2 * where + 1 , mid + 1 , IR , pos , nw ) ;
        }
        tr[ where ] = max ( tr[ 2 * where ] , tr[ 2 * where + 1 ] ) ;
    }
    int query ( int where , int IL , int IR , int CURL , int CURR ) {
        if ( IL > IR || CURL > CURR ) { return -MAXN ; }
        if ( IR < CURL || CURR < IL ) { return -MAXN ; }
        if ( CURL <= IL && IR <= CURR ) { return tr[ where ] ; }
        int mid = ( IL + IR ) / 2 ;
        return max ( query ( 2 * where , IL , mid , CURL , CURR ) , query ( 2 * where + 1 , mid + 1 , IR , CURL , CURR ) ) ;
    }
};
Tree w ;

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

vector < pair < int , int > > srt_aux ;

void dfs ( int vertex , int prv , int ori ) {
    int cnt = 0 , oth = 0 ;
    if ( st[ vertex ] <= st[ ori ] && en[ ori ] <= en[ vertex ] ) {
        int lst = get_prv ( ori , lvl[ vertex ] + 1 ) ;
        cnt = n - comp[ lst ] ;
        oth = comp[ ori ] ;
    }
    else if ( st[ ori ] <= st[ vertex ] && en[ vertex ] <= en[ ori ] ) {
        int lst = get_prv ( vertex , lvl[ ori ] + 1 ) ;
        cnt = comp[ vertex ] ;
        oth = n - comp[ lst ] ;
    }
    else {
        cnt = comp[ vertex ] ;
        oth = comp[ ori ] ;
    }
    // ans[ cnt ] = max ( ans[ cnt ] , w.query ( 1 , 1 , n , cnt , n ) + d[ vertex ] + 1 ) ;
    srt_aux.push_back ( { cnt , d[ vertex ] } ) ;
    ans[ min ( cnt , oth ) ] = max ( ans[ min ( cnt , oth ) ] , d[ vertex ] + 1 ) ;
    for ( auto x : v[ vertex ] ) {
        if ( used[ x ] == 1 || x == prv ) { continue ; }
        dfs ( x , vertex , ori ) ;
    }
}

void upd ( int vertex , int prv , int ori ) {
    int cnt = 0 , oth = 0 ;
    if ( st[ vertex ] <= st[ ori ] && en[ ori ] <= en[ vertex ] ) {
        int lst = get_prv ( ori , lvl[ vertex ] + 1 ) ;
        cnt = n - comp[ lst ] ;
        oth = comp[ ori ] ;
    }
    else if ( st[ ori ] <= st[ vertex ] && en[ vertex ] <= en[ ori ] ) {
        int lst = get_prv ( vertex , lvl[ ori ] + 1 ) ;
        cnt = comp[ vertex ] ;
        oth = n - comp[ lst ] ;
    }
    else {
        cnt = comp[ vertex ] ;
        oth = comp[ ori ] ;
    }
    w.update ( 1 , 1 , n , cnt , d[ vertex ] ) ;
    for ( auto x : v[ vertex ] ) {
        if ( used[ x ] == 1 || x == prv ) { continue ; }
        upd ( x , vertex , ori ) ;
    }
}

void rem ( int vertex , int prv , int ori ) {
    int cnt = 0 , oth = 0 ;
    if ( st[ vertex ] <= st[ ori ] && en[ ori ] <= en[ vertex ] ) {
        int lst = get_prv ( ori , lvl[ vertex ] + 1 ) ;
        cnt = n - comp[ lst ] ;
        oth = comp[ ori ] ;
    }
    else if ( st[ ori ] <= st[ vertex ] && en[ vertex ] <= en[ ori ] ) {
        int lst = get_prv ( vertex , lvl[ ori ] + 1 ) ;
        cnt = comp[ vertex ] ;
        oth = n - comp[ lst ] ;
    }
    else {
        cnt = comp[ vertex ] ;
        oth = comp[ ori ] ;
    }
    w.update ( 1 , 1 , n , cnt , -1 ) ;
    for ( auto x : v[ vertex ] ) {
        if ( used[ x ] == 1 || x == prv ) { continue ; }
        rem ( x , vertex , ori ) ;
    }
}

void decompose ( int vertex ) {
    total = 0 , d[ vertex ] = 0 ;
    init ( vertex , -1 ) ;
    vertex = get_cen ( vertex , -1 ) ;
    total = 0 , d[ vertex ] = 0 ;
    init ( vertex , -1 ) ;
    used[ vertex ] = 1 ;

    for ( auto x : v[ vertex ] ) {
        if ( used[ x ] == 1 ) { continue ; }
        srt_aux.clear ( ) ;
        dfs ( x , vertex , vertex ) ;
        sort ( srt_aux.begin ( ) , srt_aux.end ( ) ) ;
        int mx = 0 ;
        for ( int i = srt_aux.size ( ) - 1 ; i >= 0 ; -- i ) {
            mx = max ( mx , srt_aux[ i ].second ) ;
            int cnt = srt_aux[ i ].first ;
            ans[ cnt ] = max ( ans[ cnt ] , w.query ( 1 , 1 , n , cnt , n ) + mx + 1 ) ;
        }
        upd ( x , vertex , vertex ) ;
    }
    for ( auto x : v[ vertex ] ) {
        if ( used[ x ] == 1 ) { continue ; }
        rem ( x , vertex , vertex ) ;
    }
    for ( auto x : v[ vertex ] ) {
        if ( used[ x ] == 1 ) { continue ; }
        decompose ( x ) ;
    }
}

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

void solve ( ) {
    w.init ( 1 , 1 , n ) ;
    decompose ( 1 ) ;
    for ( int i = n / 2 ; i >= 1 ; -- i ) {
        ans[ i ] = max ( ans[ i ] , ans[ i + 1 ] ) ;
    }
    for ( int i = 1 ; i <= n ; ++ i ) {
        if ( ( i % 2 ) == 1 ) { cout << "1\n" ; }
        else { cout << max ( 1 , ans[ i / 2 ] ) << "\n" ; }
    }
}


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

Compilation message (stderr)

meetings2.cpp: In function 'void upd(int, int, int)':
meetings2.cpp:132:19: warning: variable 'oth' set but not used [-Wunused-but-set-variable]
  132 |     int cnt = 0 , oth = 0 ;
      |                   ^~~
meetings2.cpp: In function 'void rem(int, int, int)':
meetings2.cpp:155:19: warning: variable 'oth' set but not used [-Wunused-but-set-variable]
  155 |     int cnt = 0 , oth = 0 ;
      |                   ^~~

• Subtask 1: 0 / 4
• Subtask 2: 0 / 16
• Subtask 3: 0 / 80