제출 #865172

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
865172		maks007	Cat in a tree (BOI17_catinatree)	C++14	0 / 100	3 ms	18064 KiB

catinatree

// Bismi ALlah
#include "bits/stdc++.h"
 
using namespace std;
 
#define int long long
 
int dp[1501][1501];
 
signed main () {
	int n, d;	
	cin >> n >> d;
	vector <int> g[n];
	memset(dp, 0, sizeof(dp));
	function <void(int,int)> dfs=[&](int v, int p) {
		vector <int> child;
		for(auto u : g[v]) {
			if(u == p) continue;
			dfs(u, v);
			child.push_back(u);
		}
		for(int Dist = 1500; Dist >= 0; Dist --) {
			if(Dist == 0) {
				int temp = 1;
				for(auto other : child) {
					temp += dp[other][d-1];
				}
				dp[v][Dist] = max(temp, dp[v][Dist]);
			}
			int sum = 0;
			for(auto other : child) {
				sum += max(dp[other][max(0LL, Dist-1)], dp[other][Dist]);
			}	
			dp[v][Dist] = max(sum, dp[v][Dist]);
		}
	};
	for(int i = 1; i < n; i ++) {
		int p;
		cin >> p;
		g[i].push_back(p);
		g[p].push_back(i);
	}
	dfs(0, -1);
	int ans = -1e9;
	for(int i = 0; i <= 1500; i ++) ans = max(ans, dp[0][i]);
/*	for(int i = 0; i < n; i ++) {
		for(int j = 0; j < d; j ++) {
			cout << i << " " << j << " " << dp[i][j] << "\n"; 
		}
	}*/
	cout << ans;
	return 0;
}

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