Submission #1074515

---

Source Code Expand

#include <iostream>
#include <vector>
#include <set>
#include <cassert>
using namespace std;
int main() {
  int N;
  vector<int> a;
  vector<int> win_count;
  vector<int> depth;
  cin >> N;
  a = vector<int>(N);
  win_count = vector<int>(N);
  depth = vector<int>(N);
  for(int i = 1 ; i < N; i++) {
    cin >> a[i];
    a[i]--;
    win_count[a[i]]++;
  }

  // 誰にも勝っていない人を探す
  vector<int> loser, nloser;
  for(int i = 0; i < N; i++) {
    if(win_count[i] == 0) loser.push_back(i);
  }
  while(!loser.empty()) {
    nloser.clear();
    for(int k: loser) {
      //cout << k + 1 << "->" << a[k] + 1 << endl;
      int winner = a[k];
      win_count[winner]--;
      if(win_count[winner] == 0 && winner != 0) nloser.push_back(winner);
      depth[winner] = max(depth[k], depth[winner]) + 1;
    }
    //cout << endl;
    loser = nloser;
  }
  assert(win_count[0] == 0);
  cout << depth[0] << endl;
  return 0;
}

Submission Info

Judge Result