SRM537 Div2 Hard

925
とりあえず、グラフにする。
あるトーストを学ぶために食べるトーストの枚数は最小で１、最大でルートまでの距離
全ての頂点に関して試す。

点数も1000より低いし、本番でも40人以上が通してるけど、そんなに簡単とは思えなかった。

class PrinceXToastbook {
public:
  double eat(vector <int> P)
  {
    const int N = P.size();
    bool vis[N];

    vector<double> v[N];
   
    for (int i = 0, j; i < N; ++i) {
      fill(vis, vis + N, false);
      double depth = 1;
      for (j = i; P[j] != -1; j = P[j]) {
        if (vis[j]) {
          depth = 0;
          break;
        }
        ++depth;
        vis[j] = true;
      }
      if (depth) v[j].push_back(depth);
    }

    double ret = 0;
    for (int i = 0; i < N; ++i) {
      if (v[i].empty()) continue;
      for (int j = 0; j < v[i].size(); ++j) {
        double n = 1.0;
        for (int k = 1; k <= v[i][j]; ++k) {
          n /= k;
        }
        ret += n;
      }
    }
    return ret;
  }
};