Submission #1053476

#	Time	Username	Problem	Language	Result	Execution time	Memory
1053476		PanosPask	Cat in a tree (BOI17_catinatree)	C++14	0 / 100	1 ms	384 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 d2 = 0; d2 < v2.size(); d2++) {
        int d1 = D - d2;
        if (d1 >= v1.size()) {
            continue;
        }

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

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

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