Submission #375902

#	Time	Username	Problem	Language	Result	Execution time	Memory
375902		ntabc05101	Cat in a tree (BOI17_catinatree)	C++14	100 / 100	110 ms	18944 KiB

catinatree

#include<bits/stdc++.h>

const int max_n=200000;

int n, d;
std::vector<int> adjList[5+max_n];

std::pair<int, int> dfs(int vertex, int parent=-1) {
        std::vector< std::pair<int, int> > v;
        for (auto& to: adjList[vertex]) {
                if (to!=parent) {
                        v.push_back(dfs(to, vertex));
                }
        }

        if (v.empty()) {
                return std::make_pair(1, 1);
        }

        std::sort(begin(v), end(v), std::greater< std::pair<int, int> >());
        int pos=1;
        while (pos<v.size() and v[pos].first+v[pos-1].first>=d) ++pos;
        --pos;

        int ret=pos+1;
        for (auto& _: v) ret+=_.second-1;

        if (v.back().first>=d) {
                ++ret;
                return std::make_pair(1, ret);
        }
        
        return std::make_pair(v[pos].first+1, ret);
}

int main() {
        std::ios_base::sync_with_stdio(0); std::cin.tie(0);

        std::cin>>n>>d;
        for (int i=1, x; i<n; ++i) {
                std::cin>>x;
                adjList[x].push_back(i);
        }
        
        std::cout<<dfs(0).second<<"\n";

        return 0;
}

Compilation message (stderr)

catinatree.cpp: In function 'std::pair<int, int> dfs(int, int)':
catinatree.cpp:22:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |         while (pos<v.size() and v[pos].first+v[pos-1].first>=d) ++pos;
      |                ~~~^~~~~~~~~

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