http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=ACPC2017Day1&pid=C
解説
http://judge.u-aizu.ac.jp/onlinejudge/creview.jsp?rid=2536699&cid=ACPC2017Day1
ok[i] := ツイートが表示できるか
まず規則1と規則2で表示できるか確認する。
次は、規則2から幅優先探索で規則3を見る。
このとき、dp[i]:=規則2が適用されたツイートから返信先を辿ってくるときの残り辿れる回数の最大値
を更新しながら規則3を満たすやつを確認していく。
あとは、ok[i]==1のやつを数えて答え。
int N, K, A[101010]; int ok[101010]; vector<int> E[101010]; int ein[101010], dp[101010], vis[101010]; //-------------------------------------------------------------------------------------------------- void _main() { cin >> N >> K; rep(i, 0, N) cin >> A[i]; rep(i, 0, N) { if (A[i] == 0) ok[i] = 1; else { E[i].push_back(A[i] - 1); ein[A[i] - 1]++; } } rep(i, 0, N) if (ein[i] == 0) ok[i] = 1; queue<int> q; rep(i, 0, N) if (ein[i] == 0 && 0 < E[i].size()) { q.push(i); dp[i] = K; } while (!q.empty()) { int i = q.front(); q.pop(); if (vis[i]) continue; vis[i] = 1; if (dp[i] == 0) continue; ok[i] = 1; fore(to, E[i]) { dp[to] = max(dp[to], dp[i] - 1); q.push(to); } } int ans = 0; rep(i, 0, N) if (ok[i]) ans++; cout << ans << endl; }