Submission #1053397

#	Time	Username	Problem	Language	Result	Execution time	Memory
1053397		PanosPask	Cat in a tree (BOI17_catinatree)	C++14	0 / 100	0 ms	344 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);
    }

    // Only calculate the distances at which d1 will be minimum
    for (int d1 = 0; d1 < v2.size() && d1 <= D - d1; d1++) {
        int d2 = D - d1;
        if (d2 >= v2.size()) {
            continue;
        }

        // We want the node from v2 to be at least d2 distance away
        makemax(v1[d1], v1[d1] + v2[d2]);
    }

    // Only calculate the distances at which d2 will be minimum
    for (int d2 = 0; d2 < v2.size() && d2 <= D - d2; d2++) {
        int d1 = D - d2;
        if (d1 >= v1.size()) {
            continue;
        }

        makemax(v1[d2], v1[d1] + v2[d2]);
    }

    for (int dist = v2.size() - 1; dist >= 0; dist--) {
        makemax(v1[dist], v2[dist]);
    }
    // Only need to propagate from v2 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(-INF);

        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:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |     for (int d1 = 0; d1 < v2.size() && d1 <= D - d1; d1++) {
      |                      ~~~^~~~~~~~~~~
catinatree.cpp:32:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |         if (d2 >= v2.size()) {
      |             ~~~^~~~~~~~~~~~
catinatree.cpp:41:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     for (int d2 = 0; d2 < v2.size() && d2 <= D - d2; d2++) {
      |                      ~~~^~~~~~~~~~~
catinatree.cpp:43:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |         if (d1 >= v1.size()) {
      |             ~~~^~~~~~~~~~~~
catinatree.cpp: In function 'int main()':
catinatree.cpp:79:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |     scanf("%d %d", &N, &D);
      |     ~~~~~^~~~~~~~~~~~~~~~~
catinatree.cpp:86:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |         scanf("%d", &p);
      |         ~~~~~^~~~~~~~~~

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