Submission #1079454

#	Time	Username	Problem	Language	Result	Execution time	Memory
1079454		andrei_iorgulescu	Cat in a tree (BOI17_catinatree)	C++14	100 / 100	74 ms	26576 KiB

catinatree

#include <bits/stdc++.h>

using namespace std;

int n,d;
vector<int> g[200005], f[200005];
int t[200005];
int h[200005];

void dfs(int nod)
{
    for (auto fiu : f[nod])
    {
        h[fiu] = 1 + h[nod];
        dfs(fiu);
    }
}

int dist[200005];

void mark(int nod)
{
    queue<int> q;
    q.push(nod);
    dist[nod] = 0;
    while (!q.empty())
    {
        int x = q.front();
        q.pop();
        if (dist[x] == d)
            break;
        for (auto vecin : g[x])
        {
            if (dist[vecin] > dist[x] + 1)
            {
                dist[vecin] = dist[x] + 1;
                q.push(vecin);
            }
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n >> d;
    d--;
    for (int i = 1; i < n; i++)
    {
        cin >> t[i];
        f[t[i]].push_back(i);
        g[i].push_back(t[i]);
        g[t[i]].push_back(i);
    }
    dfs(0);
    for (int i = 0; i < n; i++)
        dist[i] = 1e9;
    vector<int> uf;
    for (int i = 0; i < n; i++)
        uf.push_back(i);
    sort(uf.begin(), uf.end(), [](int A, int B){return h[A] > h[B];});
    int ans = 0;
    for (auto it : uf)
    {
        if (dist[it] > d)
        {
            ans++;
            mark(it);
        }
    }
    cout << ans;
    return 0;
}

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