Submission #1260498

#	Time	Username	Problem	Language	Result	Execution time	Memory
1260498		4o2a	Cat in a tree (BOI17_catinatree)	C++20	100 / 100	183 ms	169156 KiB

catinatree

#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 = min(s, (D+1)/2) - 1; d >= 1; --d)
        dp[u][d] = max((d+1 < x ? dp[u][d+1] : 0), 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)

catinatree.cpp: In function 'int main()':
catinatree.cpp:78:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |         freopen(_F".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
catinatree.cpp:79:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |         freopen(_F".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
catinatree.cpp:83:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |         freopen("test.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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