Submission #866215

---

Source Code Expand

#include <bits/stdc++.h>
#include <stdio.h>
#include <stdlib.h>

#include <algorithm>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <utility>
#include <vector>

#define rep(i, n) for (int i = 0; i < static_cast<int>(n); ++i)
// #define iter(a) __typeof(a.begin())
#define FOR(it, a) for (auto it = a.begin(); it != a.end(); ++it)
#define F first
#define S second
#define SZ(a) static_cast<int>((a).size())
#define sz(a) SZ(a)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define ALL(a) (a).begin(), (a).end()
using namespace std;

typedef int64_t ll;
typedef pair<int, int> PI;
typedef pair<ll, ll> PL;
typedef uint64_t ull;

#ifdef ONLINE_JUDGE
#define PR(...) (void(0))
#else
#define PR(...) \
  do { cerr << "line : " << __LINE__ << ", " << endl;  \
    pr(#__VA_ARGS__, __VA_ARGS__); } while (0)

template<class T>
void pr(const string& name, T t) {
  cerr << name << ": " << t << endl;
}
template<typename T, typename ... Types>
void pr(const string& names, T t, Types ... rest) {
  auto p = names.find(',');
  cerr << names.substr(0, p) << ": " << t << ", ";
  pr(string(names, p + 1), rest ...);
}
#endif

template<class T, class U> ostream& operator<<(
    ostream& o, const pair<T, U>& v) {
  return o << "(" << v.F << ", " << v.S << ")";
}
template<class T> ostream& operator<<(
    ostream& o, const vector<T>& v) {
  o << "{"; rep(i, SZ(v)) o << (i?", ":"") << v[i]; return o << "}"; }
template<class T, class U> ostream& operator<<(
    ostream& o, const map<T, U>& v) {
  o << "{"; for (const auto& e : v) o << e << ", "; return o << "}"; }
template<class T, class U> ostream& operator<<(
    ostream& o, const unordered_map<T, U>& v) {
  o << "{"; for (const auto& e : v) o << e << ", "; return o << "}"; }
template<class T> ostream& operator<<(ostream& o, const set<T>& v) {
  o << "{"; for (const auto& e : v) o << e << ", "; return o << "}"; }
template<class T> string to_s(const T& v) {
  ostringstream is; is << v; return is.str(); }

const int dx[]={0, 1,  0, -1,  1, 1, -1, -1, 0};
const int dy[]={1, 0, -1,  0, -1, 1,  1, -1, 0};

#define endl '\n'

vector<int> G[100000+100];

int main(int argc, char *argv[])
{
  ios::sync_with_stdio(0);
  cin.tie(0);

  int n, k;
  cin >> n >> k;
  int ans = 0;

  rep(i, n){
    int a;
    cin >> a;
    if(i == 0){
      ans += a != 1;
      continue;
    }
    G[a].pb(i + 1);
  }

  vector<int> q;
  q.pb(1);
  while(true){
    rep(i, k){
      vector<int> nq;
      for(auto v : q){
        for(auto ne : G[v])
          nq.pb(ne);
      }
      q = nq;
    }
    if(q.empty()) break;
    for(auto a : q)
      ans += SZ(G[a]);
  }

  cout << ans << endl;
}

Submission Info

Judge Result