Submission #358310

#	Time	Username	Problem	Language	Result	Execution time	Memory
358310		Bill_00	Cat in a tree (BOI17_catinatree)	C++14	100 / 100	174 ms	84588 KiB

catinatree

#include <bits/stdc++.h>
#define pb push_back
#define ll long long
#define ff first
#define ss second
#define N 200001
using namespace std;
vector<int>child[N];
int n,d;
struct res{
	deque<int>dp;
	int size(){
		return dp.size();
	}
};
void attach(res &root,res &children){
	if(root.size()<children.size()) swap(root,children);
	res combined;
	combined.dp=children.dp;
	for(int i=0;i<children.size();i++){
		int other=max(d-i,i);
		if(other<children.size()){
			combined.dp[i]=max(combined.dp[i],root.dp[i]+children.dp[other]);
		}
		if(other<root.size()){
			combined.dp[i]=max(combined.dp[i],root.dp[other]+children.dp[i]);
		}
	}
	int maximum=0;
	for(int i=children.size();i>=1;i--){
		maximum=max(maximum,combined.dp[i-1]);
		root.dp[i-1]=max(maximum,root.dp[i-1]);
	}
}
res dfs(int node){
	res ans;
	ans.dp.push_back(1);
	for(int children:child[node]){
		res branch=dfs(children);
		branch.dp.push_front(branch.dp.front());
		attach(ans,branch);
	}
	return ans;
}
int main(){
	ios_base::sync_with_stdio(NULL);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> n >> d;
	for(int i=1;i<n;i++){
		int k;
		cin >> k;
		child[k].pb(i);
	}
	cout << dfs(0).dp.front();

}

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