Submission #569066

#	Time	Username	Problem	Language	Result	Execution time	Memory
569066		minhcool	Cat in a tree (BOI17_catinatree)	C++17	11 / 100	93 ms	596 KiB

catinatree

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define foru(i, l, r) for(int i = l; i <= r; i++)
#define ford(i, r, l) for(int i = r; i >= l; i--)

typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;

const int N = 1e3 + 5;

const int oo = 1e18 + 7, mod = 1e9 + 7;

int n, d;
vector<int> Adj[N];

int dist[N][N];

void dfs(int u, int p, int root){
	for(auto v : Adj[u]){
		if(v == p) continue;
		dist[root][v] = dist[root][u] + 1;
		dfs(v, u, root);
	}
}

void process(){
	cin >> n >> d;
	for(int i = 1; i < n; i++){
		int x;
		cin >> x;
		Adj[x].pb(i);
		Adj[i].pb(x);
	}
	for(int i = 0; i < n; i++){
		dfs(i, i, i);
	}
	int mx = -1;
	for(int i = 0; i < (1LL << n); i++){
		vector<int> vc;
		for(int j = 0; j < n; j++) if(i & (1LL << j)) vc.pb(j);
		bool ck = 1;
		for(auto it : vc){
			for(auto it2 : vc){
				if(it == it2) continue;
				ck &= (dist[it][it2] >= d);
			}
		}
		if(ck) mx = max(mx, (int)vc.size());
	}
	cout << mx;
}

signed main(){
	ios_base::sync_with_stdio(0);
	process();
}

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