Submission #681349

#	Time	Username	Problem	Language	Result	Execution time	Memory
681349		andrei_marciuc	Cat in a tree (BOI17_catinatree)	C++14	100 / 100	323 ms	244340 KiB

catinatree

#include <iostream>
#include <vector>
#include <queue> 
using namespace std;

const int MAX = 2e5 + 2;

vector<int> G[ MAX ];
deque<int> dp[ MAX ];
int second[ MAX ];
int height[ MAX ];
int child[ MAX ];
int maxx[ MAX ];
int n, d;

void calc( int nod ) {
    for( const int& it : G[ nod ] ) {
        calc( it );
        if( height[ nod ] < height[ it ] + 1 ) {
            child[ nod ] = it;
            second[ nod ] = height[ nod ];
            height[ nod ] = height[ it ] + 1;
        } else if( second[ nod ] < height[ it ] + 1 )
            second[ nod ] = height[ it ] + 1;
    }
}
 
void dfs1( int nod ) {
    for( const int& it : G[ nod ] )
        dfs1( it );

    for( int i = 0; i <= second[ nod ]; i++ )
        maxx[ i ] = 0;

    for( const int &it : G[ nod ] )
        for( int j = 1; j <= min( height[ it ] + 1, min( second[ nod ], d / 2 ) ); j++ )
            maxx[ j ] = max( maxx[ j ], dp[ it ][ j - 1 ] - ( ( d - j - 1 <= height[ it ] ) ? dp[ it ][ d - j - 1 ] : 0 ) );

    int dp0 = 1;
    for( const int &it : G[ nod ] )
        if( height[ it ] >= d - 1 )
            dp0 += dp[ it ][ d - 1 ];

    if( child[ nod ] )
        swap( dp[ nod ], dp[ child[ nod ] ] );

    dp[ nod ].push_front( dp0 );
    for( const int &it : G[ nod ] )
        if( it != child[ nod ] )
            for( int j = 1; j <= min( height[ it ] + 1, d - 1 ); j++ )
                dp[ nod ][ j ] += dp[ it ][ j - 1 ];

    for( int j = 1; j <= min( d / 2, second[ nod ] ); j++ )
        dp[ nod ][ j ] = ( ( d - j <= height[ nod ] ) ? dp[ nod ][ d - j ] : 0 ) + maxx[ j ];
    for( int j = second[ nod ]; j >= 0; j-- )
        if( j + 1 <= height[ nod ] )
            dp[ nod ][ j ] = max( dp[ nod ][ j + 1 ], dp[ nod ][ j ] );
}
 
int main()
{
    cin >> n >> d;
    int x;
    for( int i = 2; i <= n; i++ ) {
        cin >> x;
        G[ ++x ].push_back( i );
    }

    calc( 1 );
    dfs1( 1 );

    cout << dp[ 1 ][ 0 ] << '\n';
    return 0;
}

• Subtask 1: 11 / 11
• Subtask 2: 40 / 40
• Subtask 3: 49 / 49