はまやんはまやんはまやん

hamayanhamayan's blog

Displayed tweets [ACPC2017 Day1 C]

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;
}