Overview

This problem involves simulating a power grid represented as a directed graph, where substations whose load exceeds their durability value experience cascading blackouts, and we must determine all substations that ultimately lose power.

Analysis

Each substation has a “durability value” \(T_i\) and a “load” defined for it. In the initial state, the load equals the number of incoming edges (power lines) to that substation. If the load exceeds the durability value, that substation experiences a blackout. Since a blacked-out substation can no longer transmit power, the load on downstream substations increases.

To simulate this cascading effect, we need to process blacking-out substations in order. However, rather than simply processing substations whose load exceeds their durability in an arbitrary order, we need to process them starting from the “most unstable substation.” That is, we prioritize processing the one with the largest difference \(load[i] - T[i]\).

A priority queue (heap) is ideal for this kind of “prioritize extracting the element that most strongly satisfies a condition” operation. This allows us to efficiently select the most unstable substation each time.

Additionally, since a blacked-out substation should no longer have any influence, we manage this information with a flag. Furthermore, load updates are only performed on substations that have not blacked out.

Algorithm

1. Graph Construction
   Using an adjacency list out_edges[u], manage the destination substations of edges going out from each substation \(u\). Simultaneously, compute the initial load (in-degree) of each substation.

2. Initial State Preparation
   Compute the initial load of each substation, and add substations whose load exceeds their durability to the priority queue. At this point, the priority is set to \(-(load[i] - T[i])\) so that elements are extracted in order of largest difference (= most unstable first).

3. Simulation
   Repeat the following steps:

   • Extract the most unstable substation \(s\) from the priority queue.
   • If it has already blacked out, skip it.
   • Perform the blackout processing and add it to the result list.
   • Increase the load of each substation \(v\) that is a destination of edges from substation \(s\), and if its load exceeds its durability, add it to the queue.

4. Output Results
   Sort the list of blacked-out substations in ascending order and output them. If there are none, output -1.

Complexity

• Time complexity: \(O((N + M) \log N)\)
  • Heap operations are performed for each vertex and edge. Each heap operation is \(O(\log N)\).
• Space complexity: \(O(N + M)\)
  • The graph, various arrays, and heap size are proportional to the number of vertices and edges.

Implementation Notes

• Store (negative of (load - durability), vertex number) in the priority queue so that the most unstable substation can be efficiently extracted.

• Use flag management to track whether a substation has already blacked out, preventing duplicate processing.

• Since input can be large, use sys.stdin.read for fast reading.

  Source Code

import sys
from collections import deque
import heapq

input = sys.stdin.read

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    idx = 0
    N = int(data[idx]); idx += 1
    M = int(data[idx]); idx += 1
    
    T = [0] * (N+1)
    for i in range(1, N+1):
        T[i] = int(data[idx]); idx += 1

    # グラフ構築: adj[v] = list of u such that edge u->v exists
    indeg = [0] * (N+1)
    out_edges = [[] for _ in range(N+1)]  # u -> [v1, v2, ...]
    
    for _ in range(M):
        u = int(data[idx]); idx += 1
        v = int(data[idx]); idx += 1
        out_edges[u].append(v)
        indeg[v] += 1

    # 現在の負荷
    load = indeg[:]
    
    # 停電したか
    stopped = [False] * (N+1)
    
    # 停電候補を管理する優先度付きキュー（負荷 - 耐久値が大きい順）
    # タイブレーカーとして、番号が小さい順
    heap = []
    for i in range(1, N+1):
        if load[i] > T[i]:
            heapq.heappush(heap, (-(load[i] - T[i]), i))
    
    result = []

    while heap:
        # 最も不安定な変電所を取り出す
        neg_diff, s = heapq.heappop(heap)
        if stopped[s] or load[s] <= T[s]:
            continue  # すでに処理済み or 実際には条件を満たさない
        
        stopped[s] = True
        result.append(s)
        
        # 送電先の負荷を増やす
        for v in out_edges[s]:
            if not stopped[v]:
                load[v] += 1
                if load[v] > T[v]:
                    heapq.heappush(heap, (-(load[v] - T[v]), v))

    if result:
        result.sort()
        print(' '.join(map(str, result)))
    else:
        print(-1)

if __name__ == "__main__":
    main()

This editorial was generated by qwen3-coder-480b.