Overview

This problem asks us to determine, for each query, “the number of starting vertices \(S\) from which all vertices in a directed graph can be reached within at most \(K_j\) steps.”

Analysis

1. Rephrasing the Problem

Let’s organize the rumor propagation rules in graph terminology. Consider a directed graph where students are “vertices” and transmission relationships are “directed edges.”

Consider the condition “between step \(0\) and step \(K_j\), every student receives the rumor at least once.” A student \(i\) receiving the rumor at step \(t\) (\(0 \le t \le K_j\)) is equivalent to the shortest path length (shortest distance) from the starting vertex \(S\) to student \(i\) being at most \(K_j\).

Therefore, the condition for all students to receive the rumor by step \(K_j\) can be decomposed into the following two conditions: 1. All vertices are reachable from the starting vertex \(S\). 2. The shortest distance from the starting vertex \(S\) to the farthest vertex is at most \(K_j\).

Let \(D(S)\) denote the maximum shortest distance from starting vertex \(S\) to all vertices (if not all vertices are reachable, we define \(D(S) = \infty\)). Then, the condition for query \(K_j\) can be very simply rephrased as “find the number of \(S\) satisfying \(D(S) \le K_j\).”

2. Considering Optimization

The number of queries \(Q\) can be up to \(2 \times 10^5\), which is very large, so searching the graph for each query would exceed the time limit (TLE).

However, the number of vertices \(N\) is at most \(2000\), which is relatively small. Therefore, we take the approach of precomputing the shortest distances from every vertex \(S\) (\(1 \le S \le N\)) as the starting point.

If we precompute \(D(S)\) for each \(S\), we can then prepare a prefix sum array recording the distribution of \(D(S)\) values, allowing us to answer each query in \(O(1)\).

---

Algorithm

1. Shortest Path Search from Each Starting Vertex (BFS) For each vertex \(S \in \{1, 2, \ldots, N\}\) as the starting point, perform a breadth-first search (BFS).

   • If the number of vertices visited by BFS is less than \(N\), not all vertices are reachable, so this \(S\) cannot spread the rumor to everyone regardless of the number of steps. In this case, set \(D(S) = \infty\) (in implementation, \(N+1\)).
   • If the number of visited vertices equals \(N\), the shortest distance to the last visited vertex (the vertex at the tail of the BFS queue) is \(D(S)\).

2. Frequency Array and Prefix Sum Computation Prepare an array counts of size \(N+2\) and tally the values of \(D(S)\) for each \(S\).

   • counts[d] = the number of starting vertices \(S\) whose maximum shortest distance \(D(S)\) is exactly \(d\)

Create a prefix sum array pref from this counts. - pref[k] = the number of starting vertices \(S\) with \(D(S) \le k\) (i.e., the number of starting vertices from which the rumor reaches everyone within \(k\) steps)

1. Answering Queries For each query \(K_j\), answer as follows:
   • If \(K_j \ge N\): it can never take more than \(N\) steps, so output pref[N].
   • If \(K_j < N\): output pref[K_j].

---

Complexity

• Time Complexity: \(O(N(N + M) + Q)\)

  • BFS from each vertex takes \(O(N + M)\). Performing this \(N\) times gives \(O(N(N + M))\) for the preprocessing graph search. Since \(N \le 2000, M \le 50000\), the worst case is approximately \(10^8\) operations, which is well within the time limit for a lightweight BFS with small constant factors.
  • Query processing only involves accessing the prefix sum array, so it takes \(O(1)\) per query and \(O(Q)\) overall.

• Space Complexity: \(O(N + M)\)

  • \(O(N + M)\) for storing the adjacency list of the graph, and \(O(N)\) for the BFS arrays and prefix sum array.

---

Implementation Notes

To execute approximately \(10^8\) loop iterations within the time limit in Python, several optimization techniques are effective.

• Avoiding array reallocation If you reinitialize the dist array (the array recording distances) with [-1] * N for each BFS, the initialization overhead becomes non-negligible. In the presented code, only the vertices actually visited during BFS (those that entered the queue) are reset to -1 in a targeted manner, reducing initialization time from \(O(N)\) to \(O(\text{visited})\) (the actual number of explored vertices), achieving significant speedup.

• Fast I/O By reading all input at once using sys.stdin.read and outputting all results together with sys.stdout.write, the I/O bottleneck is eliminated.

  Source Code

import sys

def solve():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    M = int(input_data[1])
    Q = int(input_data[2])
    
    adj = [[] for _ in range(N)]
    idx = 3
    for _ in range(M):
        u = int(input_data[idx]) - 1
        v = int(input_data[idx+1]) - 1
        adj[u].append(v)
        idx += 2
        
    adj = tuple(tuple(x) for x in adj)
    
    dist = [-1] * N
    queue = [0] * N
    counts = [0] * (N + 2)
    
    for s in range(N):
        dist[s] = 0
        queue[0] = s
        head = 0
        tail = 1
        while head < tail:
            u = queue[head]
            head += 1
            nd = dist[u] + 1
            for v in adj[u]:
                if dist[v] == -1:
                    dist[v] = nd
                    queue[tail] = v
                    tail += 1
        if tail < N:
            counts[N+1] += 1
        else:
            max_d = dist[queue[N-1]]
            counts[max_d] += 1
            
        for i in range(tail):
            dist[queue[i]] = -1
            
    pref = [0] * (N + 2)
    cur = 0
    for i in range(N + 2):
        cur += counts[i]
        pref[i] = cur
        
    ans = []
    for _ in range(Q):
        k = int(input_data[idx])
        idx += 1
        if k >= N:
            ans.append(str(pref[N]))
        else:
            ans.append(str(pref[k]))
            
    sys.stdout.write('\n'.join(ans) + '\n')

if __name__ == '__main__':
    solve()

---

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