Overview

For each city, compute “the total capacity of connected power lines \(T_i\)” and count the number of cities where this is less than the demand \(S_i\) (i.e., cities with insufficient power).

Analysis

The amount of power \(T_i\) that can be supplied to city \(i\) is the sum of capacities of all power lines that have city \(i\) as an endpoint. In other words, each power line \((U_j, V_j, W_j)\) contributes \(W_j\) to each of its two endpoint cities.

For example, if a power line is \((1,3,5)\), then \(+5\) is added to \(T_1\) of city 1, and \(+5\) is also added to \(T_3\) of city 3.

A naive approach of “for each city, scan all power lines and sum up those connected to it” would result in \(O(NM)\) in the worst case, since both the number of cities \(N\) and the number of power lines \(M\) can be up to \(2 \times 10^5\). This is far too slow (approximately \(4\times 10^{10}\) operations).

Instead, we reverse the perspective: process each power line only once and add its capacity to the totals of both endpoint cities. This allows us to compute \(T_i\) for all cities efficiently.

Algorithm

1. Prepare an array \(T\) of length \(N\), initialized to all \(0\) (\(T[i]\) represents the suppliable power for city \(i\)).
2. For each power line \((U, V, W)\) read from input:
   • \(T[U] \mathrel{+}= W\)
   • \(T[V] \mathrel{+}= W\) (Convert city numbers to 0-indexed.)
3. Finally, count and output the number of cities \(i\) satisfying the condition \(T_i < S_i\).

Complexity

• Time complexity: \(O(N + M)\) (process each power line once, then scan all cities once)
• Space complexity: \(O(N)\) (arrays for \(S\) and \(T\))

Implementation Notes

• City numbers are 1-indexed in the input, so subtract - 1 to convert to 0-indexed internally.

• \(W_j\) and \(S_i\) can be up to \(10^9\), and the sum can involve up to \(2\times 10^5\) power lines, but Python’s integers do not overflow, so there is no concern.

• Since the input size is large, we read all input at once using sys.stdin.buffer.read() and process it efficiently with an iterator.

  Source Code

import sys

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

    for _ in range(M):
        u = next(it) - 1
        v = next(it) - 1
        w = next(it)
        T[u] += w
        T[v] += w

    ans = sum(1 for i in range(N) if T[i] < S[i])
    print(ans)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.