解いた問題

8/24/2012

SRM435 Div2 Medium

500

やるだけ。



class CellRemoval {
public:
  int cellsLeft(vector <int> p, int del)
  {
    if (p[del] == -1) return 0;

    const int size = p.size();
    int cnt[size];
    fill(cnt, cnt + size, 0);

    for (int i = 0; i < size; ++i) {
      for (int n = i; p[n] != -1; n = p[n]) {
        ++cnt[n];
      }
    }

    int ret = count(cnt, cnt + size, 1);
    for (int i = 0; i < size; ++i) {
      if (cnt[i] != 1) continue;
      for (int n = i; p[n] != -1; n = p[n]) {
        if (n == del) {
          --ret;
          break;
        }
      }
    }

    return ret;
  }
};