Submission #554179

#	Time	Username	Problem	Language	Result	Execution time	Memory
554179		Alexandruabcde	Cat in a tree (BOI17_catinatree)	C++14	100 / 100	73 ms	24308 KiB

catinatree

#include <bits/stdc++.h>

using namespace std;

constexpr int NMAX = 2e5 + 5;

int N, D;
vector <int> G[NMAX];

void Read () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N >> D;

    for (int i = 2; i <= N; ++ i ) {
        int x;
        cin >> x;
        ++ x;

        G[x].push_back(i);
    }
}

int dp[NMAX];
int dist[NMAX];
int Last[NMAX];
bool used[NMAX];

bool cmp (int a, int b) {
    return dist[a] < dist[b];
}

void Dfs (int Node, int dad = 0) {
    bool fr = 1;
    for (auto it : G[Node]) {
        if (it == dad) continue;

        fr = 0;
        Dfs(it, Node);
    }

    if (fr) {
        used[Node] = true;
        Last[Node] = Node;
        dp[Node] = 1;
        dist[Node] = 0;
        return;
    }

    vector <int> sons;
    for (auto it : G[Node]) {
        if (it == dad) continue;

        dp[Node] += dp[it];
        sons.push_back(it);
    }

    sort(sons.begin(), sons.end(), cmp);
    int worst = sons[0];
    for (int i = 1; i < sons.size(); ++ i ) {
        if (dist[worst] + dist[sons[i]] + 2 < D) {
            used[Last[worst]] = false;
            worst = sons[i];
            -- dp[Node];
        }
    }

    Last[Node] = Last[worst];
    dist[Node] = dist[worst] + 1;

    if (dist[Node] >= D) {
        dp[Node] ++;
        dist[Node] = 0;
        Last[Node] = Node;
        used[Node] = true;
    }
}

int main () {
    Read();
    Dfs(1);

    cout << dp[1] << '\n';

    /*
    for (int i = 1; i <= N; ++ i )
        if (used[i]) cout << i << " ";
    */

    return 0;
}

Compilation message (stderr)

catinatree.cpp: In function 'void Dfs(int, int)':
catinatree.cpp:61:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |     for (int i = 1; i < sons.size(); ++ i ) {
      |                     ~~^~~~~~~~~~~~~

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