Overview

In a mechanism where rumors spread synchronously on a directed graph, the problem asks to determine, for each starting point \(S\), whether the rumor reaches everyone within \(K\) steps. The key insight is the observation that “the step at which each student first receives the rumor = the shortest distance from the starting point.”

Analysis

Key Observation: First Arrival Step = Shortest Distance

By the problem’s definition, \(A_t\) is “the set of students who receive the rumor at step \(t\),” and students who have heard the rumor before can be included again. However, if we focus on the step at which each student \(v\) first receives the rumor \(f(v) = \min\{t \mid v \in A_t\}\), this coincides with the shortest distance on the directed graph \(d(S, v)\) from the starting point \(S\) to \(v\).

Proof sketch:

• \(f(v) \leq d(S, v)\): If there exists a shortest path \(S = w_0 \to w_1 \to \cdots \to w_d = v\), then since \(w_0 \in A_0\), we get \(w_1 \in A_1\), and since \(w_1 \in A_1\), we get \(w_2 \in A_2\), … propagating in order guarantees \(v \in A_d\).
• \(f(v) \geq d(S, v)\): If \(v \in A_t\), then by induction, there exists some \(u \in A_{t-1}\) with an edge \((u,v)\), so \(d(S,v) \leq d(S,u) + 1 \leq t\).

Reduction to Queries

For a query \(K_j\), \(S\) satisfies the condition if and only if “for all students \(v\), \(d(S, v) \leq K_j\).” In other words, we need to count the number of \(S\) satisfying:

\[\max_{1 \leq v \leq N} d(S, v) \leq K_j\]

Algorithm

1. BFS from all sources: For each student \(S\) (\(1 \leq S \leq N\)), perform BFS on the directed graph starting from \(S\) and compute the shortest distances to all vertices. If there exists an unreachable vertex, set \(\text{max\_dist}[S] = \infty\) (implemented as \(N+1\)); otherwise, set \(\text{max\_dist}[S] = \max_v d(S, v)\).

2. Frequency distribution preprocessing: Count the number of occurrences for each value of \(\text{max\_dist}[S]\) and compute prefix sums. Precompute \(\text{ans}[k] = |\{S \mid \text{max\_dist}[S] \leq k\}|\) for \(k = 0, 1, \ldots, N\).

3. Query answering: For each query \(K_j\), output \(\text{ans}[K_j]\) in \(O(1)\).

Concrete Example

Graph: \(1 \to 2,\ 2 \to 3,\ 1 \to 3\) with \(N=3\). - \(S=1\): \(d(1,1)=0,\ d(1,2)=1,\ d(1,3)=1\) → \(\text{max\_dist}=1\) - \(S=2\): \(d(2,3)=1\) but \(d(2,1)=\infty\) → \(\text{max\_dist}=\infty\) - \(S=3\): Cannot reach anywhere → \(\text{max\_dist}=\infty\)

The answer for \(K=1\) is \(1\) (only \(S=1\) is valid).

Complexity

• Time complexity: \(O(N(N + M) + Q)\)
  • \(N\) BFS runs each taking \(O(N + M)\), queries answered in \(O(1)\) each after preprocessing
• Space complexity: \(O(N + M)\)
  • Adjacency list for the graph and arrays for BFS

Implementation Notes

• BFS uses a standard queue-based implementation, adding each vertex to the queue only when it is visited for the first time. Although the problem’s definition of \(A_t\) allows revisits, only the first arrival matters, so standard BFS is sufficient.

• To correctly handle cases where unreachable vertices exist, count the number of vertices visited by BFS, and if it is less than \(N\), set \(\text{max\_dist}[S]\) to \(N+1\) (a value larger than the maximum possible \(K\), which is \(N\)).

• Since the number of queries can be up to \(2 \times 10^5\), use a precomputed prefix sum table for constant-time responses.

• Use fast input reading (sys.stdin.buffer.read()) to avoid TLE even in Python.

  Source Code

import sys
from collections import deque

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    Q = int(input_data[idx]); idx += 1
    
    # adjacency list
    adj = [[] for _ in range(N)]
    for i in range(M):
        u = int(input_data[idx]) - 1; idx += 1
        v = int(input_data[idx]) - 1; idx += 1
        adj[u].append(v)
    
    # For each starting node S, we need to find the minimum step at which each node
    # is first reached. But the propagation rule is BFS-like but with a twist:
    # only nodes reached at step t-1 propagate at step t.
    # This is actually exactly BFS on the directed graph!
    # Because in BFS, each node is visited exactly once, and it propagates only once
    # (when it's first discovered). The "set A_t" in the problem corresponds to
    # the BFS frontier at distance t.
    #
    # Wait, but the problem says a node CAN appear in A_t multiple times (at different steps).
    # However, for the purpose of "first time reached", we only care about the minimum t.
    # 
    # Actually, let me re-read. A_t is defined purely based on A_{t-1}, not on "unvisited" nodes.
    # So A_t can contain nodes already visited. This is NOT standard BFS.
    #
    # Example: 1->2, 2->1, 1->3. Start S=1.
    # A_0 = {1}, A_1 = {2,3}, A_2 = {1} (from 2->1), A_3 = {2,3}, ...
    # Node 3 is first reached at step 1. That's fine.
    # But node 1 is in A_0 and A_2. Node 2 is in A_1 and A_3.
    #
    # For the "first time" each node is reached, we want min T_i for each i.
    # The first time a node v is reached is the shortest path distance from S to v 
    # in the directed graph. Because: A_0 = {S}. A_1 = out-neighbors of S. 
    # A_2 = out-neighbors of A_1. Even though nodes can repeat, the first occurrence
    # of any node v is at the shortest path distance from S to v.
    #
    # So for each S, the minimum step at which node v is reached = shortest directed 
    # distance from S to v (infinity if unreachable).
    #
    # For query K: S is valid iff max over all v of dist(S,v) <= K.
    # i.e., all nodes are reachable from S within K steps.
    
    # For each S, compute BFS shortest distances, find max distance (or infinity if some unreachable)
    # Then for query K, count how many S have max_dist[S] <= K.
    
    # N <= 2000, M <= 5000, so N BFS operations: O(N*(N+M)) = O(2000*7000) = 14M, fine.
    
    max_dist = [0] * N  # max_dist[s] = max shortest distance from s to any node
    
    for s in range(N):
        dist = [-1] * N
        dist[s] = 0
        queue = deque([s])
        max_d = 0
        reached = 1
        while queue:
            u = queue.popleft()
            d = dist[u]
            for v in adj[u]:
                if dist[v] == -1:
                    dist[v] = d + 1
                    if dist[v] > max_d:
                        max_d = dist[v]
                    reached += 1
                    queue.append(v)
        if reached < N:
            max_dist[s] = N + 1  # unreachable, effectively infinity
        else:
            max_dist[s] = max_d
    
    # Precompute answer for each K from 0 to N
    # ans[k] = number of S with max_dist[S] <= k
    count = [0] * (N + 2)
    for s in range(N):
        md = max_dist[s]
        if md <= N:
            count[md] += 1
    
    # prefix sum
    ans = [0] * (N + 1)
    ans[0] = count[0]
    for k in range(1, N + 1):
        ans[k] = ans[k - 1] + count[k]
    
    out = []
    for _ in range(Q):
        K = int(input_data[idx]); idx += 1
        out.append(str(ans[K]))
    
    sys.stdout.write('\n'.join(out) + '\n')

main()

---

This editorial was generated by claude4.6opus-thinking.