Overview

This problem asks you to simulate a phenomenon where blackouts spread in a chain reaction through a power grid represented as a directed graph, when the load on substations exceeds their durability values.

Analysis

In the initial state, the load on each substation equals its in-degree (the number of incoming power lines). When a blackout occurs, the load increases by 1 for each substation connected by outgoing power lines from the blacked-out substation. If this increase causes another substation’s load to exceed its durability value, the blackout further cascades.

The key observation is that the chain of blackouts spreads like a “Breadth-First Search (BFS).” Since a substation that has already blacked out never needs to be processed again, and each substation blacks out at most once, an efficient simulation is possible.

A naive approach would be to check all substations each time to find those satisfying the blackout condition, but this would take \(O(N^2)\) time in the worst case, which exceeds the time limit under the constraint \(N \leq 2 \times 10^5\).

Algorithm

1. Initialization: Record the initial load (in-degree) and durability value of each substation.
2. Queue initialization: Add all substations that satisfy the blackout condition (load \(>\) durability value) in the initial state to a queue, and mark them as blacked out.
3. Simulation via BFS: Repeat the following until the queue is empty:
   • Dequeue a substation and process all outgoing power lines from it.
   • If the destination substation has not yet blacked out, increase its load by 1.
   • If the load after the increase exceeds the durability value, add that substation to the queue and mark it as blacked out.
4. Output results: Output the numbers of all substations that ultimately blacked out, in ascending order.

Complexity

• Time complexity: \(O(N + M)\)
  • Each substation and each power line is processed at most once.
• Space complexity: \(O(N + M)\)
  • \(O(N + M)\) for the graph representation, and \(O(N)\) for various arrays.

Implementation Notes

• Representing the graph as an adjacency list enables efficient traversal.

• A stopped array is used to track whether each substation has blacked out, preventing duplicate processing.

• Using a queue allows the chain of blackouts to be simulated in a natural order.

• Don’t forget to handle the case where the output is empty (output -1).

  Source Code

import sys
from collections import deque

def main():
    data = sys.stdin.read().split()
    if not data:
        print(-1)
        return
        
    it = iter(data)
    n = int(next(it)); m = int(next(it))
    T = [0] * (n+1)
    for i in range(1, n+1):
        T[i] = int(next(it))
        
    graph = [[] for _ in range(n+1)]
    in_deg = [0] * (n+1)
    
    for _ in range(m):
        u = int(next(it)); v = int(next(it))
        graph[u].append(v)
        in_deg[v] += 1
        
    initial_load = in_deg[:]
    current_load = initial_load[:]
    
    stopped = [False] * (n+1)
    q = deque()
    
    for i in range(1, n+1):
        if current_load[i] > T[i]:
            q.append(i)
            stopped[i] = True
            
    while q:
        s = q.popleft()
        for neighbor in graph[s]:
            if not stopped[neighbor]:
                current_load[neighbor] += 1
                if current_load[neighbor] > T[neighbor]:
                    stopped[neighbor] = True
                    q.append(neighbor)
                    
    result = []
    for i in range(1, n+1):
        if stopped[i]:
            result.append(i)
            
    if not result:
        print(-1)
    else:
        print(" ".join(map(str, result)))

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.