Overview

This is a problem where you compare each city’s “demand \(S_i\)” with the “total transmission capacity \(T_i\)” of its connected power lines, and find the total number of cities where \(T_i < S_i\).

Analysis

The key to solving this problem lies in how to efficiently compute the total transmission capacity \(T_i\) for each city.

If we search for connected power lines one by one for each city \(i\), it could take \(O(N \times M)\) time in the worst case, which will not meet the time limit under the given constraints (\(N, M \leq 2 \times 10^5\)).

However, by iterating through the power line information in order and performing the operation “add capacity \(W\) to the supply of the 2 cities connected by that power line”, we can determine \(T_i\) for all cities by examining each power line only once.

Specifically, we proceed with the following steps: 1. Prepare an array \(T\) of length \(N\) and initialize all elements to \(0\). 2. For each power line \((U_j, V_j, W_j)\): - Add \(W_j\) to the supply of city \(U_j\) (\(T_{U_j} \leftarrow T_{U_j} + W_j\)) - Add \(W_j\) to the supply of city \(V_j\) (\(T_{V_j} \leftarrow T_{V_j} + W_j\)) 3. After processing all power lines, determine whether \(T_i < S_i\) for each \(i\).

Algorithm

1. Read input: Read the number of cities \(N\), the number of power lines \(M\), and the demand \(S_i\) for each city.
2. Aggregate supply:
   • Initialize an array T that holds the total supply for each city to \(0\).
   • Read the information for \(M\) power lines, and for each power line, add the transmission capacity \(W\) to the elements of T corresponding to the indices of the 2 cities it connects.
3. Judgment and counting:
   • For \(i = 1\) to \(N\), check whether T[i] < S[i] holds.
   • Count the number of cities satisfying the condition (cities with power shortage).
4. Output: Output the counted value as the answer.

Complexity

• Time complexity: \(O(N + M)\)
  • Reading the demands takes \(O(N)\), processing the power lines takes \(O(M)\), and the final judgment takes \(O(N)\). This is sufficiently fast within the given constraints.
• Space complexity: \(O(N)\)
  • \(O(N)\) memory is used for the arrays holding the demands \(S\) and the total supply \(T\).

Implementation Notes

• Index adjustment: The input city numbers range from \(1\) to \(N\), but arrays in programs typically start from \(0\), so subtracting \(1\) from the city numbers makes processing smoother.

• Fast I/O: Since \(N\) and \(M\) can be large, in Python, reading all input at once using sys.stdin.read().split() or similar methods can help reduce execution time.

• Handling large numbers: The demand \(S_i\) and capacity \(W_j\) can be up to \(10^9\), and the total supply \(T_i\) may exceed that. In Python, there is no limit on integer size, so calculations can be performed without worrying about overflow.

  Source Code

import sys

def solve():
    # Read all input data at once and split by whitespace
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # Use an iterator to process the input tokens one by one efficiently
    it = map(int, input_data)
    
    try:
        # N: Number of cities, M: Number of power lines
        N = next(it)
        M = next(it)
        
        # S: Demand for each city (S[0] to S[N-1])
        S = [next(it) for _ in range(N)]
        
        # T: Total supply capacity for each city (initialized to 0)
        T = [0] * N
        
        # Process each of the M power lines
        for _ in range(M):
            u = next(it) - 1
            v = next(it) - 1
            w = next(it)
            # Each power line contributes its capacity to both cities it connects
            T[u] += w
            T[v] += w
            
        # Count the number of cities that are power deficient (T_i < S_i)
        deficient_count = 0
        for i in range(N):
            if T[i] < S[i]:
                deficient_count += 1
        
        # Output the total count
        print(deficient_count)
        
    except StopIteration:
        pass

if __name__ == '__main__':
    solve()

This editorial was generated by gemini-3-flash-thinking.