oj.uz

Submission #540934

# Submission time Handle Problem Language Result Execution time Memory
540934 2022-03-22T02:42:28 Z chonka Meetings 2 (JOI21_meetings2) C++
100 / 100
 3498 ms 47536 KB 
#include<bits/stdc++.h>
using namespace std ;

#define MAXN 200007
#define LOG 19

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 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 = -MAXN ;
        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 ) ;
        }
        for ( auto [ cnt , dep ] : srt_aux ) {
            w.update ( 1 , 1 , n , cnt , dep ) ;
        }
    }
    for ( auto x : v[ vertex ] ) {
        if ( used[ x ] == 1 ) { continue ; }
        rem ( x , vertex , vertex ) ;
    }
    int sz = v[ vertex ].size ( ) ;
    for ( int p = sz - 1 ; p >= 0 ; -- p ) {
        int x = v[ vertex ][ p ] ;
        if ( used[ x ] == 1 ) { continue ; }
        srt_aux.clear ( ) ;
        dfs ( x , vertex , vertex ) ;
        sort ( srt_aux.begin ( ) , srt_aux.end ( ) ) ;
        int mx = -MAXN ;
        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 ) ;
        }
        for ( auto [ cnt , dep ] : srt_aux ) {
            w.update ( 1 , 1 , n , cnt , dep ) ;
        }
    }
    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

meetings2.cpp: In function 'void rem(int, int, int)':
meetings2.cpp:133:19: warning: variable 'oth' set but not used [-Wunused-but-set-variable]
  133 |     int cnt = 0 , oth = 0 ;
      |                   ^~~
meetings2.cpp: In function 'void decompose(int)':
meetings2.cpp:173:20: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  173 |         for ( auto [ cnt , dep ] : srt_aux ) {
      |                    ^
meetings2.cpp:194:20: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  194 |         for ( auto [ cnt , dep ] : srt_aux ) {
      |                    ^

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 2 ms 5076 KB Output is correct
8 Correct 2 ms 4948 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 3 ms 4948 KB Output is correct
11 Correct 3 ms 4948 KB Output is correct
12 Correct 3 ms 5076 KB Output is correct
13 Correct 4 ms 4948 KB Output is correct
14 Correct 4 ms 4948 KB Output is correct
15 Correct 3 ms 4948 KB Output is correct
16 Correct 2 ms 4948 KB Output is correct
17 Correct 2 ms 4948 KB Output is correct
18 Correct 3 ms 4948 KB Output is correct
19 Correct 3 ms 4948 KB Output is correct
20 Correct 2 ms 5076 KB Output is correct
21 Correct 3 ms 4948 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 2 ms 5076 KB Output is correct
8 Correct 2 ms 4948 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 3 ms 4948 KB Output is correct
11 Correct 3 ms 4948 KB Output is correct
12 Correct 3 ms 5076 KB Output is correct
13 Correct 4 ms 4948 KB Output is correct
14 Correct 4 ms 4948 KB Output is correct
15 Correct 3 ms 4948 KB Output is correct
16 Correct 2 ms 4948 KB Output is correct
17 Correct 2 ms 4948 KB Output is correct
18 Correct 3 ms 4948 KB Output is correct
19 Correct 3 ms 4948 KB Output is correct
20 Correct 2 ms 5076 KB Output is correct
21 Correct 3 ms 4948 KB Output is correct
22 Correct 14 ms 5708 KB Output is correct
23 Correct 15 ms 5708 KB Output is correct
24 Correct 15 ms 5688 KB Output is correct
25 Correct 14 ms 5708 KB Output is correct
26 Correct 14 ms 5704 KB Output is correct
27 Correct 13 ms 5696 KB Output is correct
28 Correct 17 ms 5640 KB Output is correct
29 Correct 17 ms 5712 KB Output is correct
30 Correct 14 ms 5716 KB Output is correct
31 Correct 14 ms 5700 KB Output is correct
32 Correct 25 ms 5820 KB Output is correct
33 Correct 29 ms 5928 KB Output is correct
34 Correct 6 ms 5588 KB Output is correct
35 Correct 6 ms 5588 KB Output is correct
36 Correct 15 ms 5716 KB Output is correct
37 Correct 7 ms 5732 KB Output is correct
38 Correct 17 ms 5816 KB Output is correct

Subtask #3
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 2 ms 5076 KB Output is correct
8 Correct 2 ms 4948 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 3 ms 4948 KB Output is correct
11 Correct 3 ms 4948 KB Output is correct
12 Correct 3 ms 5076 KB Output is correct
13 Correct 4 ms 4948 KB Output is correct
14 Correct 4 ms 4948 KB Output is correct
15 Correct 3 ms 4948 KB Output is correct
16 Correct 2 ms 4948 KB Output is correct
17 Correct 2 ms 4948 KB Output is correct
18 Correct 3 ms 4948 KB Output is correct
19 Correct 3 ms 4948 KB Output is correct
20 Correct 2 ms 5076 KB Output is correct
21 Correct 3 ms 4948 KB Output is correct
22 Correct 14 ms 5708 KB Output is correct
23 Correct 15 ms 5708 KB Output is correct
24 Correct 15 ms 5688 KB Output is correct
25 Correct 14 ms 5708 KB Output is correct
26 Correct 14 ms 5704 KB Output is correct
27 Correct 13 ms 5696 KB Output is correct
28 Correct 17 ms 5640 KB Output is correct
29 Correct 17 ms 5712 KB Output is correct
30 Correct 14 ms 5716 KB Output is correct
31 Correct 14 ms 5700 KB Output is correct
32 Correct 25 ms 5820 KB Output is correct
33 Correct 29 ms 5928 KB Output is correct
34 Correct 6 ms 5588 KB Output is correct
35 Correct 6 ms 5588 KB Output is correct
36 Correct 15 ms 5716 KB Output is correct
37 Correct 7 ms 5732 KB Output is correct
38 Correct 17 ms 5816 KB Output is correct
39 Correct 1753 ms 35960 KB Output is correct
40 Correct 1673 ms 35692 KB Output is correct
41 Correct 1650 ms 36012 KB Output is correct
42 Correct 1609 ms 36496 KB Output is correct
43 Correct 1660 ms 36416 KB Output is correct
44 Correct 1647 ms 36376 KB Output is correct
45 Correct 3324 ms 42676 KB Output is correct
46 Correct 3498 ms 47536 KB Output is correct
47 Correct 423 ms 35852 KB Output is correct
48 Correct 256 ms 36032 KB Output is correct
49 Correct 1901 ms 37452 KB Output is correct
50 Correct 500 ms 36996 KB Output is correct
51 Correct 1948 ms 46052 KB Output is correct