Submission #707330

#	Time	Username	Problem	Language	Result	Execution time	Memory
707330		four_specks	Cat in a tree (BOI17_catinatree)	C++17	100 / 100	140 ms	19536 KiB

catinatree

#include <bits/stdc++.h>

using namespace std;

namespace
{
} // namespace

void solve()
{
    int n, d;
    cin >> n >> d;

    vector<int> p(n, -1);
    vector<vector<int>> adj(n);
    for (int u = 1; u < n; u++)
    {
        cin >> p[u];
        adj[p[u]].push_back(u);
    }

    vector<int> depth(n, -1);
    {
        queue<int> q;
        depth[0] = 0;
        q.push(0);
        while (!q.empty())
        {
            int u = q.front();
            q.pop();

            for (int v : adj[u])
            {
                depth[v] = depth[u] + 1;
                q.push(v);
            }
        }
    }

    vector<vector<int>> occ(n);
    for (int u = 0; u < n; u++)
        occ[depth[u]].push_back(u);

    int cnt = 0;

    vector<int> level(n, INT_MAX);
    for (int i = n - 1; i >= 0; i--)
    {
        for (int s : occ[i])
        {
            if (level[s] == INT_MAX)
            {
                cnt++;

                queue<int> q;
                level[s] = 0;
                q.push(s);
                while (!q.empty())
                {
                    int u = q.front();
                    q.pop();

                    if (level[u] == d - 1)
                        continue;

                    for (int v : adj[u])
                    {
                        if (level[u] + 1 < level[v])
                        {
                            level[v] = level[u] + 1;
                            q.push(v);
                        }
                    }
                    if (p[u] != -1 && level[u] + 1 < level[p[u]])
                    {
                        level[p[u]] = level[u] + 1;
                        q.push(p[u]);
                    }
                }
            }
        }
    }

    cout << cnt << '\n';
}

int main()
{
    ios_base::sync_with_stdio(false), cin.tie(NULL);

    solve();

    return 0;
}

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