Overview

Instead of directly simulating the chain of blackouts, we formulate conditions that “the set of substations that ultimately do not lose power” must satisfy, and solve by deleting vertices that cannot satisfy the conditions using a queue (similar to core decomposition).

Analysis

1. How the load changes

The initial load of substation \(v\) is its in-degree \(\mathrm{in}(v)\).
Furthermore, when there is a power line \(u \to v\), if \(u\) loses power (and \(v\) is still alive), the load on \(v\) increases by \(+1\).

In other words, the final load of a surviving substation \(v\) is the sum of:

• The initial portion \(\mathrm{in}(v)\)
  
• The increase from blacked-out predecessors (the number of incoming edges to \(v\) whose source has lost power)

2. Writing conditions in terms of the “survival set” (this is the key insight)

Let \(A\) (Alive) be the set of substations that ultimately do not lose power. For \(v \in A\), there are \(\mathrm{in}(v)\) incoming edges to \(v\) in total, of which:

• Number of incoming edges whose source is also alive: \(\mathrm{in}_A(v)\)
• Number of incoming edges whose source has lost power: \(\mathrm{in}(v)-\mathrm{in}_A(v)\)

For \(v\) remaining in \(A\), the load increases by the number of blacked-out in-neighbors, so the final load is

[ \mathrm{in}(v) + \bigl(\mathrm{in}(v)-\mathrm{in}_A(v)\bigr) = 2\mathrm{in}(v)-\mathrm{in}_A(v) ]

To survive, the load must not exceed the durability when the chain settles, so

[ 2\mathrm{in}(v)-\mathrm{in}_A(v) \le T_v ]

Rearranging this gives

[ \mathrm{in}_A(v) \ge 2\mathrm{in}(v) - T_v ]

Therefore, for each vertex \(v\), there is a defined “number of incoming edges from the survival set \(A\) required to survive”: [ \text{need}(v)=\max(0,\;2\mathrm{in}(v)-T_v) ]

Concrete example

When \(\mathrm{in}(v)=3,\;T_v=4\):
\(\text{need}(v)=2\cdot3-4=2\).
“At least 2 incoming edges from the survival set are needed” = “at most 1 in-neighbor is allowed to lose power.”
This matches the intuition that starting from an initial load of 3, it can withstand an increase of at most 1, up to 4.

3. Why the naive approach is problematic

If we repeatedly “select a vertex with load \(>T\) and black it out” step by step, we need selection and updates at each step.
However, from the analysis above, the final state is determined solely by “whether the survival set \(A\) satisfies the need condition,” and it is unique regardless of the order, so directly computing \(A\) is simpler and faster.

Algorithm

What we want to find is the largest set \(A\) satisfying the condition [ \forall v\in A:\ \mathrm{in}_A(v)\ge \text{need}(v) ] (i.e., what remains after deleting everything that cannot satisfy the condition).

The procedure is the following “peeling”:

1. Count the in-degree \(\mathrm{in}(v)\).
   
2. For each \(v\), compute \(\text{need}(v)=\max(0,2\mathrm{in}(v)-T_v)\).
3. Maintain in_remain[v] as the number of edges coming into \(v\) from currently remaining vertices. Initially, in_remain[v]=in(v).
4. Any vertex \(v\) with in_remain[v] < need[v] can no longer satisfy the condition and cannot survive, so add it to the queue as a deletion candidate.
5. Take a vertex \(u\) from the queue and delete it. Since \(u\) is “removed from the survival set,” for each edge \(u\to w\), decrease in_remain[w] by 1 (the “incoming edge from the survival set” that \(u\) was providing to \(w\) is lost).
6. If this causes in_remain[w] < need[w], add \(w\) to the queue as well.
7. Repeat until the queue is empty.

The vertices deleted at the end form the “set of substations that ultimately lose power” (the complement of the survival set \(A\)).

In the code, we use: - out[u]: destinations from \(u\) (adjacency list) - in_remain[v]: number of edges coming into \(v\) from currently remaining vertices - need[v]: number of edges required to survive - removed[v]: whether the vertex has been deleted (= confirmed to lose power)

to implement the above.

Complexity

• Time complexity: \(O(N+M)\) (each vertex is deleted at most once, each edge decreases in_remain at most once)
• Space complexity: \(O(N+M)\) (adjacency list and various arrays)

Implementation Notes

• When need[v]=2*indeg[v]-T[v] is negative, clamp it to \(0\) (since requiring a “negative number of edges” from the survival set is meaningless).

• When deleting, note that we traverse out[u] to “decrease the destination’s in_remain” (when \(u\) is removed, the edges going out from \(u\) are no longer counted as “incoming edges from the survival set”).

• The same vertex may be added to the queue multiple times, so when dequeuing, check removed[u] to prevent duplicate processing.

• Output the deleted vertices (removed[i]==1) in ascending order. If none, output -1.

  Source Code

import sys
from collections import deque

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)
    N = next(it)
    M = next(it)
    T = [next(it) for _ in range(N)]

    out = [[] for _ in range(N)]
    indeg = [0] * N
    for _ in range(M):
        u = next(it) - 1
        v = next(it) - 1
        out[u].append(v)
        indeg[v] += 1

    need = [0] * N
    in_remain = indeg[:]
    q = deque()
    for i in range(N):
        ni = 2 * indeg[i] - T[i]
        if ni < 0:
            ni = 0
        need[i] = ni
        if in_remain[i] < ni:
            q.append(i)

    removed = bytearray(N)
    while q:
        u = q.popleft()
        if removed[u]:
            continue
        removed[u] = 1
        for v in out[u]:
            if removed[v]:
                continue
            in_remain[v] -= 1
            if in_remain[v] < need[v]:
                q.append(v)

    ans = [str(i + 1) for i in range(N) if removed[i]]
    if not ans:
        sys.stdout.write("-1\n")
    else:
        sys.stdout.write(" ".join(ans) + "\n")

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.