提出 #43412100

---

ソースコード 拡げる

import std;

void read(T...)(string S, ref T args) {
    auto buf = S.split;
    foreach (i, ref arg; args) {
        arg = buf[i].to!(typeof(arg));
    }
}

struct pair {
    int person;
    int span;
}

void main () {
    int N, M; readln.read(N, M);
    int[][] graph = new int[][](N, 0);

    int[] p = readln.split.to!(int[]);
    p[] -= 1;
    foreach (i; 1..N) {
        graph[p[i-1]] ~= i;
        graph[i] ~= p[i-1];
    }

    int[] insurance = new int[](N);
    foreach (i; 0..M) {
        int x, y; readln.read(x, y);
        x--;
        insurance[x] = max(insurance[x], y+1);
    }

    solve(N, M, graph, insurance);
}

void solve (int N, int M, int[][] graph, int[] insurance) {
    int[] visited = new int[](N);
    // visited[i] := -1 => 未探索 | 0 => 保険未加入者 | 1 => 保険加入者
    visited[] = -1;

    DList!int Q;
    Q.insert(0);
    if (0 < insurance[0]) {
        visited[0] = 1;
    } else {
        visited[0] = 0;
    }

    while (!Q.empty) {
        auto begin = Q.front; Q.removeFront;
        foreach (to; graph[begin]) {
            if (visited[to] == -1) {
                insurance[to] = max(insurance[to], insurance[begin]-1);
                if (0 < insurance[to]) {
                    visited[to] = 1;
                } else {
                    visited[to] = 0;
                }
                Q.insertBack(to);
            }
        }
    }

    int ans = 0;
    foreach (i; 0..N) {
        if (visited[i] == 1) {
            ans++;
        }
    }

    writeln(ans);
}

提出情報

ジャッジ結果