oj.uz

Submission #540913

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

#define MAXN 200007

int n ;
vector < int > v[ MAXN ] ;
int used[ MAXN ] ;

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

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 ] ;

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

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 ) ;
        for ( int i = subtree[ x ] + 1 ; i >= 1 ; -- i ) {
            mx_cur[ i ] = max ( mx_cur[ i ] , mx_cur[ i + 1 ] ) ;
            ans[ i ] = max ( ans[ i ] , mx_cur[ i ] + 1 + suff[ i ] ) ;
            suff[ i ] = max ( suff[ i ] , mx_cur[ i ] ) ;
        }
        for ( int i = 0 ; i <= subtree[ x ] ; ++ i ) {
            mx_cur[ i ] = -MAXN ;
        }
    }
}

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 ) ;
    }
}

void solve ( ) {
    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 3 ms 4948 KB Output is correct
2 Correct 3 ms 5020 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Incorrect 3 ms 4948 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

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

Subtask #3
0 / 80.0

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