oj.uz

Submission #540916

# Submission time Handle Problem Language Result Execution time Memory
540916 2022-03-22T01:34:43 Z chonka Meetings 2 (JOI21_meetings2) C++
0 / 100
 4 ms 5076 KB 
#include<bits/stdc++.h>
using namespace std ;

#define MAXN 200007

int n ;
vector < int > v[ MAXN ] ;
int comp[ MAXN ] , lvl[ MAXN ] ;
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 ( auto x : v[ vertex ] ) {
        if ( x == prv ) { continue ; }
        lvl[ x ] = lvl[ vertex ] + 1 ;
        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 ;

void dfs ( int vertex , int prv , int ori ) {
    int cnt = 0 ;
    if ( st[ vertex ] <= st[ ori ] && en[ ori ] <= en[ vertex ] ) {
        cnt = n - comp[ vertex ] + 1 ;
    }
    else { cnt = comp[ vertex ] ; }
    ans[ cnt ] = max ( ans[ cnt ] , w.query ( 1 , 1 , n , cnt , n ) + 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 ;
    if ( st[ vertex ] <= st[ ori ] && en[ ori ] <= en[ vertex ] ) {
        cnt = n - comp[ vertex ] + 1 ;
    }
    else { cnt = comp[ vertex ] ; }
    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 ;
    if ( st[ vertex ] <= st[ ori ] && en[ ori ] <= en[ vertex ] ) {
        cnt = n - comp[ vertex ] + 1 ;
    }
    else { cnt = comp[ vertex ] ; }
    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 ( int i = 0 ; i <= total ; ++ i ) {
        suff[ i ] = -MAXN ;
        mx_cur[ i ] = -MAXN ;
    }
    for ( auto x : v[ vertex ] ) {
        if ( used[ x ] == 1 ) { continue ; }
        dfs ( x , vertex , vertex ) ;
        upd ( x , vertex , vertex ) ;
    }
    for ( auto x : v[ vertex ] ) {
        if ( used[ x ] == 1 ) { continue ; }
        rem ( x , vertex , vertex ) ;
    }
}

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 ( 2 , 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 ;
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 3 ms 5076 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Incorrect 4 ms 5076 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 3 ms 5076 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Incorrect 4 ms 5076 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 3 ms 5076 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Incorrect 4 ms 5076 KB Output isn't correct
5 Halted 0 ms 0 KB -