Overview

This problem asks us to efficiently determine, for each query, “how many starting vertices \(S\) exist such that, starting from \(S\) in a directed graph, all vertices can be reached within \(K\) steps.”

Analysis

1. Modeling Rumor Propagation as a Graph

Consider a directed graph where students are “vertices” and rumor transmission relationships are “directed edges.” The rule “if student \(u\) receives a rumor, it is transmitted to student \(v\) in the next step” corresponds to traversing one edge in one step on the graph.

When student \(S\) initially receives the rumor, the step at which each student \(i\) first receives the rumor equals the length of the shortest path (minimum number of steps) from vertex \(S\) to vertex \(i\).

Therefore, the condition “between step \(0\) and step \(K\), every student receives the rumor at least once” can be rephrased in graph terminology as follows:

• “The shortest distance from starting vertex \(S\) to every other vertex is at most \(K\).”

This is further equivalent to:

• “All vertices are reachable from starting vertex \(S\), and the shortest distance from \(S\) to the farthest vertex is at most \(K\).”

2. Naive Approach and Its Limitations

If we try to determine for each query “whether trying all starting vertices \(S\) allows the rumor to reach everyone within \(K\) steps,” each determination requires BFS (Breadth-First Search) taking \(O(N + M)\) time. Doing this for all \(S\) (\(N\) vertices) and repeating for all \(Q\) queries results in a total complexity of \(O(Q \cdot N(N + M))\), which will not fit within the time limit (TLE).

3. Efficient Solution: Precomputation and Prefix Sums

By precomputing the parts that do not depend on the query \(K\), we can answer each query quickly.

1. For each vertex \(S\) (\(1 \leq S \leq N\)), perform BFS to determine the following two pieces of information:
   • The number of vertices reachable from \(S\)
   • The maximum shortest distance to any reachable vertex from \(S\) (denote this as \(D_S\))
2. If all vertices are reachable from \(S\) (i.e., the number of reachable vertices is \(N\)), record that \(D_S\). If not all vertices are reachable, the rumor will never reach everyone regardless of how many steps pass, so we ignore this case.
3. Let count_D[d] be the number of starting vertices \(S\) whose maximum shortest distance is exactly \(d\).
4. Compute the prefix sum pref of count_D. pref[k] represents “the number of starting vertices \(S\) whose maximum shortest distance is at most \(k\).”

With this precomputation, for each query \(K_j\), we can answer in \(O(1)\) by simply looking up pref[K_j].

---

Algorithm

1. Graph Construction: Create an adjacency list adj from the given transmission relationships.

2. BFS from Each Starting Vertex: For each \(S \in [1, N]\), do the following:

   • Using BFS with a queue, compute the shortest distance from starting vertex \(S\) to each other vertex.
   • Update the number of visited vertices visited_count and the maximum shortest distance max_dist.
   • After BFS completes, if visited_count == N, increment count_D[max_dist] by \(1\).

3. Prefix Sum Computation: Construct the array pref as follows:

   • pref[0] = count_D[0]
   • pref[i] = pref[i-1] + count_D[i] (\(1 \leq i \leq N\))

4. Answering Queries: For each query \(K_j\), output the following:

   • If \(K_j > N\), the maximum distance is at most \(N\), so treat \(K_j\) as \(N\).
   • Output pref[K_j].

---

Complexity

Time Complexity

• Precomputation with BFS: A single BFS takes \(O(N + M)\) time. Performing this \(N\) times gives a total of \(O(N(N + M))\).
• Prefix Sum Computation: Computing the prefix sum of an array of length \(N\) takes \(O(N)\).
• Query Processing: Answering each of the \(Q\) queries in \(O(1)\) gives a total of \(O(Q)\).

The total time complexity is \(O(N(N + M) + Q)\). Under the constraints \(N \leq 2000, M \leq 50000\), we have \(N(N+M) \approx 1.04 \times 10^8\) operations, which is easily executable within 1 second in C++.

Space Complexity

• Storing the graph’s adjacency list requires \(O(N + M)\).
• Various arrays for BFS (distances, visited flags, etc.) require \(O(N)\).

The total space complexity is \(O(N + M)\), which is very lightweight with respect to memory limits.

---

Implementation Notes

• Fast Initialization of Visited Flags: If the vis array is initialized to 0 in every iteration of the loop for each \(S\), this alone costs \(O(N^2)\) time. In the correct solution, a variable vis_id is prepared, incremented with vis_id++ at each iteration, and whether a vertex has been visited is determined by checking vis[v] == vis_id. This eliminates the need for array initialization, achieving a constant factor speedup.

  Source Code

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    // 高速な入出力
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, M, Q;
    if (!(cin >> N >> M >> Q)) return 0;

    vector<vector<int>> adj(N + 1);
    for (int i = 0; i < M; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
    }

    vector<int> dist(N + 1, -1);
    vector<int> vis(N + 1, 0);
    int vis_id = 0;

    vector<int> count_D(N + 1, 0);
    vector<int> q(N + 1);

    // 各頂点 S を始点とする BFS
    for (int S = 1; S <= N; ++S) {
        vis_id++;
        dist[S] = 0;
        vis[S] = vis_id;
        int q_head = 0, q_tail = 0;
        q[q_tail++] = S;

        int visited_count = 0;
        int max_dist = 0;

        while (q_head < q_tail) {
            int u = q[q_head++];
            visited_count++;
            max_dist = max(max_dist, dist[u]);
            for (int v : adj[u]) {
                if (vis[v] != vis_id) {
                    vis[v] = vis_id;
                    dist[v] = dist[u] + 1;
                    q[q_tail++] = v;
                }
            }
        }

        // すべての頂点に到達可能な場合のみカウント
        if (visited_count == N) {
            if (max_dist <= N) {
                count_D[max_dist]++;
            }
        }
    }

    // 累積和を計算
    vector<int> pref(N + 1, 0);
    pref[0] = count_D[0];
    for (int i = 1; i <= N; ++i) {
        pref[i] = pref[i - 1] + count_D[i];
    }

    // クエリ処理
    for (int j = 0; j < Q; ++j) {
        int K;
        cin >> K;
        if (K > N) K = N;
        cout << pref[K] << "\n";
    }

    return 0;
}

---

This editorial was generated by gemini-3.5-flash-thinking.