# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1260484 | 4o2a | Cat in a tree (BOI17_catinatree) | C++20 | 73 ms | 139592 KiB |
#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define _F "what"
using namespace std;
typedef long long ll;
constexpr int N = 2e5;
vector<deque<int>> dp(N);
vector<int> adj[N];
int n, D;
void dfs(int u)
{
int l = -1;
for (int v: adj[u])
{
dfs(v);
dp[v].push_front(0);
if (l == -1 || dp[v].size() > dp[l].size())
l = v;
}
if (l == -1)
{
dp[u].push_front(1);
return;
}
swap(dp[u], dp[l]);
int s = 0;
for (int v: adj[u])
s = max(s, (int)dp[v].size());
int x = dp[u].size();
vector<int> T(s), M(s);
for (int d = 1; d < s; ++d)
{
int rev = (1 <= D-d && D-d < x ? dp[u][D-d] : 0);
T[d] = rev;
M[d] = dp[u][d] - rev;
}
for (int v: adj[u])
{
int m = dp[v].size();
for (int d = 1; d < m; ++d)
{
if (d >= (D+1)/2)
dp[u][d] += dp[v][d];
else
{
int rev = (D-d < m ? dp[v][D-d] : 0);
T[d] += rev;
M[d] = max(M[d], dp[v][d] - rev);
}
}
dp[v].clear();
}
for (int d = 1; d < s && d < (D+1)/2; ++d)
dp[u][d] = T[d] + M[d];
dp[u][0] = max((dp[u].size() > D ? dp[u][D] : 0) + 1, dp[u][1]);
}
void solve()
{
cin>>n>>D;
for (int i = 1; i < n; ++i)
{
int x; cin>>x;
adj[x].pb(i);
}
dfs(0);
cout<<dp[0][0];
}
int main()
{
if (fopen(_F".INP", "r"))
{
freopen(_F".INP", "r", stdin);
freopen(_F".OUT", "w", stdout);
}
else if (fopen("test.inp", "r"))
{
freopen("test.inp", "r", stdin);
//freopen("test.out", "w", stdout);
}
ios_base::sync_with_stdio(0);
cin.tie(0);
int Test = 1; //cin>>Test;
while (Test--) solve();
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |