Submission #1063045

#	Time	Username	Problem	Language	Result	Execution time	Memory
1063045		IdanRosen	Cat in a tree (BOI17_catinatree)	C++98	100 / 100	97 ms	90508 KiB

catinatree

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pii;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;

ll n, k;
vector<vector<ll> > adj;

struct dp_t {
    // dp[i] the maximum ans for this subtree if every chosen node is at least d distance from the subtree root
    // the condition dp[i] >= dp[i + 1] holds
    deque<ll> dp;

    ll max_ans() {
        if (dp.empty()) return 0;
        else return dp[0];
    }

    ll dp_at(ll depth) {
        if (depth < dp.size()) return dp[depth];
        else return 0;
    }

    ll sz() { return dp.size(); }
};

void combine(dp_t &res, dp_t &other) {
    dp_t combined;

    for (ll depth = 0; depth < min(res.sz(), other.sz()); depth++) {
        ll best = max({
            res.dp_at(depth),
            other.dp_at(depth),
            res.dp_at(depth) + other.dp_at(max(k - depth, depth)),
            other.dp_at(depth) + res.dp_at(max(k - depth, depth))
        });
        combined.dp.push_back(best);
    }

    if (res.sz() < other.sz()) swap(res, other);

    ll max_val = combined.dp.back();
    for (ll i = combined.sz() - 1; i >= 0; i--) {
        max_val = max(max_val, combined.dp_at(i));
        // combined.dp[i] = max_val;
        res.dp[i] = max_val;
    }

    // res = std::move(combined);
}

dp_t dfs(ll v, ll par = -1) {
    dp_t ans;
    ans.dp.push_back(1);

    for (ll u: adj[v]) {
        if (u == par) continue;

        dp_t sub_ans = dfs(u, v);
        sub_ans.dp.push_front(sub_ans.dp[0]);
        combine(ans, sub_ans);
    }

    return ans;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> n >> k;

    adj.resize(n);
    for (ll v = 0; v < n - 1; v++) {
        ll u;
        cin >> u;
        adj[v + 1].push_back(u);
        adj[u].push_back(v + 1);
    }

    cout << dfs(0).max_ans();
}

Compilation message (stderr)

catinatree.cpp: In member function 'll dp_t::dp_at(ll)':
catinatree.cpp:25:19: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::deque<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |         if (depth < dp.size()) return dp[depth];
      |             ~~~~~~^~~~~~~~~~~

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