| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1296170 | avighna | Cat in a tree (BOI17_catinatree) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, d;
cin >> n >> d;
vector<vector<int>> adj(n);
for (int i = 1, p; i < n; ++i) {
cin >> p;
adj[p].push_back(i);
cout << p << ' ' << i << '\n';
}
if (d >= n) {
cout << "1\n";
return 0;
}
auto dfs = [&](auto &&self, int u) -> deque<int> {
deque<int> dp(n);
for (int &i : adj[u]) {
deque<int> ndp = self(self, i);
ndp.push_front(0);
ndp.pop_back();
deque<int> nndp(n);
for (int i = 0; i < ndp.size(); ++i) {
nndp[i] = max(dp[i], ndp[i]);
}
for (int i = 0; i < dp.size(); ++i) {
for (int j = 0; j < ndp.size(); ++j) {
if (i + j < d) {
continue;
}
nndp[min(i, j)] = max(nndp[min(i, j)], dp[i] + ndp[j]);
}
}
dp = nndp;
}
dp[0] = max(dp[0], dp[d] + 1);
debug(u, dp);
return dp;
};
deque<int> dp = dfs(dfs, 0);
cout << *max_element(dp.begin(), dp.end()) << '\n';
}