제출 #1272466

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1272466		elotelo966	Cat in a tree (BOI17_catinatree)	C++20	0 / 100	0 ms	332 KiB

catinatree

// kodda saçma sapan şeyler yapmış olabilirim
// bitmedi okuldan sonra tekrar bakacağım :))
#include <bits/stdc++.h>
using namespace std;
 
#define int long long
#define OYY LLONG_MAX
#define faster ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define fi first
#define se second
#define FOR for(int i=1;i<=n;i++)
#define mid (start+end)/2
#define pb push_back
#define lim 1505

typedef long long lo;

int n,d;

vector<int> v[lim];

int cev;

map<int,int> dp[lim];

int dep[lim];

inline void pre(int node,int ata){
	dep[node]=dep[ata]+1;
	for(auto go:v[node]){
		pre(go,node);
	}
}

inline int cal(int node,int x){
	return dep[node]+x;
}

inline void f(int node){
	dp[node][cal(node,0)]=1;
	int cur=0;
	for(auto go:v[node]){
		f(go);
		dp[node][cal(node,0)]+=dp[go][cal(go,d-1)];
		//~ if(dp[node].size()<dp[go].size()){
			//~ cur=max(cur,(int)dp[node].size());
			//~ swap(dp[node],dp[go]);
		//~ }
	}
	
	for(int j=1;j<=cur;j++){
		int tot=0,tot2=0,maxi=0;
		for(auto go:v[node]){
			tot+=dp[go][cal(go,d-j-1)];
			tot2+=dp[go][cal(go,j-1)];
			maxi=max(maxi,dp[go][cal(go,j-1)]);
		}
		for(auto go:v[node]){
			tot-=dp[go][cal(go,d-j-1)];
			tot+=dp[go][cal(go,j-1)];
			if(j<=d-j)dp[node][cal(node,j)]=max(dp[node][cal(node,j)],tot);
			tot-=dp[go][cal(go,j-1)];
			tot+=dp[go][cal(go,d-j-1)];
		}
		if(j>=d-j){
			dp[node][cal(node,j)]=max(dp[node][cal(node,j)],tot2);
		}
	}
	
	for(int j=cur;j>=0;j--){
		dp[node][cal(node,j)]=max(dp[node][cal(node,j)],dp[node][cal(node,j+1)]);
		cev=max(cev,dp[node][cal(node,j)]);
	}
}

int32_t main(){
	faster
	cin>>n>>d;
	d=min(d,n+2);
	
	FOR{
		if(i==1)continue;
		int x;cin>>x;
		x++;
		v[x].pb(i);
	}
	
	pre(1,0);
	
	f(1);
	
	FOR{
		cout<<i<<endl;
		for(int j=0;j<=d;j++){
			cout<<dp[i][j]<<" ";
		}
		cout<<endl;
	}
	
	cout<<cev<<'\n';
	
	return 0;
}

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