Submission #985572

#TimeUsernameProblemLanguageResultExecution timeMemory
985572OAleksaCat in a tree (BOI17_catinatree)C++14
0 / 100
1062 ms472 KiB
#include <bits/stdc++.h> #define f first #define s second using namespace std; const int N = 310; const int K = 18; 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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...