Submission #1149965

#	Time	Username	Problem	Language	Result	Execution time	Memory
1149965		Doncho_Bonboncho	Cat in a tree (BOI17_catinatree)	C++20	100 / 100	74 ms	28484 KiB

catinatree

#include <any>
#include <bits/stdc++.h>
#include <cstddef>
#include <deque>
#include <utility>
#include <vector>
using namespace std;
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")

#define endl "\n"

template<class T, class T2> inline bool chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline bool chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }

#ifndef LOCAL
#define cerr if(false) cerr
#endif
#define out( x ) #x << " = " << x << "  "

template<typename T, typename S> ostream& operator << (ostream &os, const pair<T, S> &p) {
	return os << "(" << p.first << ", " << p.second << ")";
}

template<typename T, typename B = decay<decltype(*begin(declval<T>()))>, typename enable_if<!is_same<T, string>::value>::type* = nullptr>
ostream& operator <<(ostream &os, const T &c) {
	bool f = false;
	os << "(";
	for(const auto &x : c) {
		if(f) {
			os << ", ";
		}
		f = true;
		os << x;
	}return os << ")";
}

typedef long long ll;
const ll mod = 1e9 + 7;
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~//

const int MAX_N = 2e5 + 10;

int n, D;

struct Deque{
    vector<int> a;
    int size(){ return int(a.size()); }
    void push_front(int x){
        a.push_back(x);
    }
    int& operator [] (int x){
        return a.rbegin()[x];
    }
    void clear(){
        vector<int>().swap(a);
    }
};

std::vector< int > v[MAX_N];
Deque dp[MAX_N];

void dfs( int x, int par = -1 ){

	dp[x].push_front( 1 );

	for( auto j : v[x] ){

		dfs( j, x );
		dp[j].push_front( dp[j][0] );
		cerr << out( x ) << out( j ) << endl;

		if( dp[j].size() > dp[x].size() ){
			std::swap( dp[j], dp[x] );
		}

		//cerr << out( dp[x] ) << out( dp[j] ) << endl;

		int szJ = dp[j].size();
		int szX = dp[x].size();
		for( int i=0 ; i < szJ ; i++ ){
			int d = std::max( i, D - i );
			int A = ( szJ > d ? dp[j][d] + dp[x][i] : dp[x][i] );
			int B = ( szX > d ? dp[x][d] + dp[j][i] : dp[x][i] );

			dp[x][i] = std::max( A, B );
		}

		for( int i=szJ -1 ; i >= 0 ; i-- ){
			if( i + 1 < szX ) chkmax( dp[x][i], dp[x][i + 1] );
		}
		dp[j].clear();
	}

}

void solve() {

	std::cin >> n >> D;
	for( int i=1 ; i < n ; i++ ){
		int a, b;
		std::cin >> a;
		b = i;
		v[a].push_back( b );
	}

	dfs( 0 );

	//cerr << out( dp[0] ) << endl;

	ll nas = dp[0][0];
	//for( auto j : dp[0] ) chkmax( nas, j );
	std::cout << nas << endl;

}

signed main() {
#ifndef LOCAL
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#endif

	int t = 1;
	//cin >> t;
	while(t --) {
		solve();
	}

	return 0;
}

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