제출 #1271446

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

catinatree

#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 405

int n,d;

vector<int> v[lim];

int cev;

int dist[lim][lim];

inline void dfs(int node,int ata,int kim,int cur){
	dist[kim][node]=cur;
	for(auto go:v[node]){
		if(go==ata)continue;
		dfs(go,node,kim,cur+1);
	}
}

inline void f(int sira,int mask){
	if(sira>n){
		bool stop=1;
		vector<int> a;
		for(int i=1;i<=n;i++){
			if(mask&(1<<i))a.pb(i);
		}
		for(auto x:a){
			for(auto y:a){
				if(x==y)continue;
				if(dist[x][y]<d)stop=0;
			}
		}
		if(stop)cev=max(cev,(int)a.size());
		return ;
	}
	f(sira+1,mask|(1<<sira));
	f(sira+1,mask);
}

int32_t main(){
	faster
	cin>>n>>d;
	
	FOR{
		if(i==1)continue;
		int x;cin>>x;
		x++;
		v[x].pb(i);
		v[i].pb(x);
	}
	
	FOR{
		dfs(i,-1,i,0);
	}
	
	f(1,0);
	
	cout<<cev<<'\n';
	
	return 0;
}

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