Submission #865031

#	Time	Username	Problem	Language	Result	Execution time	Memory
865031		maks007	Cat in a tree (BOI17_catinatree)	C++14	11 / 100	211 ms	524288 KiB

catinatree

// Bismi ALlah
#include "bits/stdc++.h"

using namespace std;

signed main () {
	int n, d;	
	cin >> n >> d;
	vector <int> g[n], dp(1 << n, 0);
	function <int(int,int,int,int)> check=[&](int v, const int mask, int p, int dist) {
		if(mask & (1 << v)) {
			if(dist >= d) return 1;
			return 0;
		}
		for(auto u : g[v]) {
			if(u == p) continue;
			if(check(u, mask, v, dist + 1) == 0) return 0;
		}
		return 1;
	};
	for(int i = 1; i < n; i ++) {
		int p;
		cin >> p;
		g[i].push_back(p);
		g[p].push_back(i);
	}
	dp[0] = 1;
	for(int mask = 0; mask < (1 << n); mask ++) {
		for(int i= 0; i < n; i ++) {
			if(mask & (1 << i)) {
				if(dp[mask ^ (1 << i)]) {
					dp[mask] |= check(i, mask ^ (1 << i), -1, 0);
				}
			}
		}
	}
	int ans = 0;
	for(int mask = 0; mask < (1 << n); mask ++) {
		if(dp[mask]) ans = max(ans, __builtin_popcount(mask));
	}
	cout << ans;
	return 0;
}

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