Submission #463948

#	Time	Username	Problem	Language	Result	Execution time	Memory
463948		blue	Cat in a tree (BOI17_catinatree)	C++17	100 / 100	264 ms	221020 KiB

catinatree

#include <iostream>
#include <deque>
using namespace std; int N, D, x, q = 0; deque<int> c[200'000];
deque<int> d(int u) {
    deque<int> q(1, 1);
    for(int v: c[u]) {
        auto a = d(v);
        if(q.size() < a.size()) swap(q, a);
        for(int i = 0; i < a.size(); i++) q[i] = max(q[i], max(a[i] + (D-i < q.size() ? q[max(D-i, i)] : 0), q[i] + (D-i < a.size() ? a[max(D-i, i)] : 0)));
        for(int i = a.size(); i >= 0; i--) if(i+1 < q.size()) q[i] = max(q[i], q[i+1]); }
    q.push_front(q.front()); return q; }
int main() {
    cin >> N >> D;
    for(int i = 1; i < N; i++) { cin >> x; c[x].push_back(i); }
    for(int r: d(0)) q = max(q, r);
    cout << q << '\n'; }

Compilation message (stderr)

catinatree.cpp: In function 'std::deque<int> d(int)':
catinatree.cpp:9:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 |         for(int i = 0; i < a.size(); i++) q[i] = max(q[i], max(a[i] + (D-i < q.size() ? q[max(D-i, i)] : 0), q[i] + (D-i < a.size() ? a[max(D-i, i)] : 0)));
      |                        ~~^~~~~~~~~~
catinatree.cpp:9:76: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 |         for(int i = 0; i < a.size(); i++) q[i] = max(q[i], max(a[i] + (D-i < q.size() ? q[max(D-i, i)] : 0), q[i] + (D-i < a.size() ? a[max(D-i, i)] : 0)));
      |                                                                        ~~~~^~~~~~~~~~
catinatree.cpp:9:122: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 |         for(int i = 0; i < a.size(); i++) q[i] = max(q[i], max(a[i] + (D-i < q.size() ? q[max(D-i, i)] : 0), q[i] + (D-i < a.size() ? a[max(D-i, i)] : 0)));
      |                                                                                                                      ~~~~^~~~~~~~~~
catinatree.cpp:10:51: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |         for(int i = a.size(); i >= 0; i--) if(i+1 < q.size()) q[i] = max(q[i], q[i+1]); }
      |                                               ~~~~^~~~~~~~~~

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