Submission #985573

#	Time	Username	Problem	Language	Result	Execution time	Memory
985573		OAleksa	Cat in a tree (BOI17_catinatree)	C++14	11 / 100	326 ms	604 KiB

catinatree

#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
const int N = 310;
const int K = 5;
int n, d;
int up[N][K], tin[N], tout[N], timer, dep[N];
vector<int> g[N];
bool anc(int a, int b) {
	return tin[a] <= tin[b] && tout[a] >= tout[b];
}
int lca(int a, int b) {
	if (anc(a, b))
		return a;
	else if (anc(b, a))
		return b;
	for (int i = K - 1;i >= 0;i--) {
		if (!anc(up[a][i], b) && up[a][i] > 0)
			a = up[a][i];
	}
	return up[a][0];
}
void dfs(int v, int p) {
	tin[v] = ++timer;
	up[v][0] = p;
	dep[v] = dep[p] + 1;
	for (int i = 1;i < K;i++)
		up[v][i] = up[up[v][i - 1]][i - 1];
	for (auto u : g[v]) {
		if (u == p)
			continue;
		dfs(u, v);
	}
	tout[v] = timer;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int tt = 1;
  //cin >> tt;
  while (tt--) {
  	cin >> n >> d;
  	for (int i = 2;i <= n;i++) {
  		int x;
  		cin >> x;
  		++x;
  		g[x].push_back(i);
  		g[i].push_back(x);
  	}
  	dfs(1, 0);
  	int ans = 0;
  	for (int mask = 1;mask < (1 << n);mask++) {
  		int ok = 1;
  		for (int i = 0;i < n;i++) {
  			if (mask >> i & 1) {
  				for (int j = 0;j < n;j++) {
  					if (i == j)
  						continue;
  					if (mask >> j & 1) {
  						int dis = dep[i + 1] + dep[j + 1] - 2 * dep[lca(i + 1, j + 1)];
  						ok &= (dis >= d);
  					}
  				}
  			}
  		}
  		if (ok) {
  			ans = max(ans, __builtin_popcount(mask));
  		}
  	}
  	cout << ans;
  }
  return 0; 
}

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