Submission #629719

#	Time	Username	Problem	Language	Result	Execution time	Memory
629719		chonka	Cat in a tree (BOI17_catinatree)	C++17	100 / 100	64 ms	20296 KiB

catinatree

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

const int MAXN = 2e5 + 7 ;

int n , k ;
vector < int > v[ MAXN ] ;

int dp[ MAXN ] , dist[ MAXN ] ;

vector < int > aux ;

void dfs ( int x ) {
    for ( auto y : v[ x ] ) {
        dfs ( y ) ;
    }
    aux.clear ( ) ;
    for ( auto y : v[ x ] ) {
        dp[ x ] += dp[ y ] ;
        if ( dist[ y ] + 1 < k ) { 
            aux.push_back ( dist[ y ] + 1 ) ;
        }
    }
    sort ( aux.begin ( ) , aux.end ( ) , greater < int > ( ) ) ;
    int sz = aux.size ( ) ;
    while ( sz >= 2 && aux[ sz - 1 ] + aux[ sz - 2 ] < k ) {
        -- sz , -- dp[ x ] ;
        aux.pop_back ( ) ;
    }
    if ( sz == 0 ) {
        ++ dp[ x ] ; dist[ x ] = 0 ;
    }
    else {
        dist[ x ] = aux.back ( ) ;
    }
}

void solve ( ) {
    cin >> n >> k ;
    for ( int i = 2 , x ; i <= n ; ++ i ) {
        cin >> x ; ++ x ;
        v[ x ].push_back ( i ) ;
    }
    dfs ( 1 ) ;
    cout << dp[ 1 ] << "\n" ;
}

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

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