Submission #134259

#	Time	Username	Problem	Language	Result	Execution time	Memory
134259		Kastanda	Cat in a tree (BOI17_catinatree)	C++11	100 / 100	153 ms	25456 KiB

catinatree

#include<bits/stdc++.h>
using namespace std;
const int N = 200005;
int n, d;
vector < int > D[N], Adj[N];
inline int Get(int v, int i)
{
    i = (int)D[v].size() - 1 - max(i, 0);
    if (i < 0)
        return 0;
    return (D[v][i]);
}
void DFS(int v)
{
    for (int &u : Adj[v])
    {
        DFS(u);
        if (D[v].size() < D[u].size())
            D[v].swap(D[u]);
        vector < int > vec(D[u].size(), 0);
        for (int i = 0; i < D[u].size(); i++)
        {
            vec[i] = max(vec[i], Get(u, i) + Get(v, max(d - i - 2, i)));
            vec[i] = max(vec[i], Get(v, i) + Get(u, max(d - i - 2, i)));
        }
        for (int i = (int)D[u].size() - 1; ~ i; i --)
        {
            int id = (int)D[v].size() - 1 - i;
            D[v][id] = max(D[v][id], vec[i]);
            if (id) D[v][id] = max(D[v][id], D[v][id - 1]);
        }
        D[u].clear(); vec.clear();
    }
    D[v].push_back(max(1 + Get(v, d - 1), Get(v, 0)));
}
int main()
{
    scanf("%d%d", &n, &d);
    for (int i = 1, p; i < n; i++)
    {
        scanf("%d", &p);
        Adj[p].push_back(i);
    }
    DFS(0);
    return !printf("%d\n", Get(0, 0));
}

Compilation message (stderr)

catinatree.cpp: In function 'void DFS(int)':
catinatree.cpp:21:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < D[u].size(); i++)
                         ~~^~~~~~~~~~~~~
catinatree.cpp: In function 'int main()':
catinatree.cpp:38:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &d);
     ~~~~~^~~~~~~~~~~~~~~~
catinatree.cpp:41:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &p);
         ~~~~~^~~~~~~~~~

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