Submission #1048193

#TimeUsernameProblemLanguageResultExecution timeMemory
1048193duckindogCat in a tree (BOI17_catinatree)C++17
100 / 100
50 ms15452 KiB
#include <bits/stdc++.h>

using namespace std;

const int N = 200'000 + 10;
int n, d;
vector<int> ad[N];

int depth[N];
int a[N];
void dfs(int u, int x) { 
  if (a[u] >= x) return;
  a[u] = x;
  for (const auto& v : ad[u]) dfs(v, x - 1);
}

int32_t main() { 
  cin.tie(0)->sync_with_stdio(0);

  cin >> n >> d;
  for (int v = 1; v < n; ++v) { 
    int u; cin >> u;
    ad[u].push_back(v);
    ad[v].push_back(u);
    depth[v] = depth[u] + 1;
  }

  int answer = 0;
  vector<int> vt(n); iota(vt.begin(), vt.end(), 0);
  sort(vt.begin(), vt.end(), [&](const auto& a, const auto& b) { 
    return depth[a] > depth[b];
  });
  for (const auto& i : vt) { 
    answer += !a[i];
    if (!a[i]) dfs(i, d);
  }

  cout << answer << "\n";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...