Submission #1053501

#	Time	Username	Problem	Language	Result	Execution time	Memory
1053501		PanosPask	Cat in a tree (BOI17_catinatree)	C++14	100 / 100	209 ms	244400 KiB

catinatree

#include <bits/stdc++.h>
#define pb push_back

using namespace std;

const int INF = 1e6;

int N, D;
vector<vector<int>> adj_list;

//dp[node][dist]: Most nodes placed in the subtree of node
// if the closest node is at least dist away from node
vector<deque<int>> dp;

void makemax(int& a, const int& b)
{
    if (a < b) {
        a = b;
    }
}

// Merge the 2 dps and store the result in d1
void merge(deque<int>& v1, deque<int>& v2)
{
    if (v1.size() < v2.size()) {
        swap(v1, v2);
    }

    vector<int> created(v2.size(), 0);
    for (int dist = 0; dist < v2.size(); dist++) {
        int counterdist = D - dist;
        if (counterdist < dist) {
            // We want dist to be the minimum distance
            counterdist = dist;
        }

        if (counterdist < v1.size()) {
            makemax(created[dist], v1[counterdist] + v2[dist]);
        }
        if (counterdist < v2.size()) {
            makemax(created[dist], v1[dist] + v2[counterdist]);
        }
    }

    for (int dist = 0; dist < v2.size(); dist++) {
        makemax(v1[dist], v2[dist]);
        makemax(v1[dist], created[dist]);
    }

    // Propagate downwards
    for (int dist = v2.size() - 2; dist >= 0; dist--) {
        makemax(v1[dist], v1[dist + 1]);
    }
}

void dfs(int node, int par)
{
    dp[node].push_back(1);

    for (auto neigh : adj_list[node]) {
        if (neigh == par) {
            continue;
        }

        dfs(neigh, node);

        // Move all of dp[neigh] one step higher
        dp[neigh].push_front(dp[neigh].front());

        merge(dp[node], dp[neigh]);
    }
}

int main(void)
{
    scanf("%d %d", &N, &D);

    adj_list.resize(N);
    dp.resize(N);

    for (int i = 1; i < N; i++) {
        int p;
        scanf("%d", &p);

        adj_list[p].pb(i);
    }

    dfs(0, 0);

    printf("%d\n", dp[0][0]);
}

Compilation message (stderr)

catinatree.cpp: In function 'void merge(std::deque<int>&, std::deque<int>&)':
catinatree.cpp:30:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |     for (int dist = 0; dist < v2.size(); dist++) {
      |                        ~~~~~^~~~~~~~~~~
catinatree.cpp:37:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |         if (counterdist < v1.size()) {
      |             ~~~~~~~~~~~~^~~~~~~~~~~
catinatree.cpp:40:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |         if (counterdist < v2.size()) {
      |             ~~~~~~~~~~~~^~~~~~~~~~~
catinatree.cpp:45:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     for (int dist = 0; dist < v2.size(); dist++) {
      |                        ~~~~~^~~~~~~~~~~
catinatree.cpp: In function 'int main()':
catinatree.cpp:76:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |     scanf("%d %d", &N, &D);
      |     ~~~~~^~~~~~~~~~~~~~~~~
catinatree.cpp:83:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |         scanf("%d", &p);
      |         ~~~~~^~~~~~~~~~

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