Overview

Given the initial stock in \(N\) warehouses, we process \(M\) instructions of the form “move \(W\) items from warehouse \(U\) to warehouse \(V\)” all at once, then find the warehouse number with the most stock (if there are ties, output the smallest number).

Analysis

The key point of this problem is how to efficiently handle the “apply all at once” operation.

Each delivery instruction \((U_j, V_j, W_j)\) affects the final stock quantities as follows: - The stock of warehouse \(U_j\) decreases by \(W_j\) - The stock of warehouse \(V_j\) increases by \(W_j\)

Although it says “apply all at once,” this is equivalent to “summing up all increases and decreases from every instruction and then applying them to the initial values.” Therefore, by reading each instruction in order and updating the current stock of the relevant warehouses through simulation, we can correctly calculate the final stock quantities.

Since \(N\) and \(M\) can be as large as \(2 \times 10^5\), we need to avoid complex processing for each instruction and instead use \(O(1)\) operations that directly update array values.

Algorithm

1. Initialization: Prepare an array \(P\) of length \(N\) and store the initial stock count for each warehouse.
2. Processing instructions: Read the \(M\) instructions one by one.
   • Decrease the stock of warehouse \(U_j\) by \(W_j\): P[U_j - 1] -= W_j
   • Increase the stock of warehouse \(V_j\) by \(W_j\): P[V_j - 1] += W_j
   • ※ Since array indices start from 0, we subtract 1 from the warehouse number to adjust.
3. Finding the maximum: Scan through array \(P\) from the beginning (warehouse 1) in order, keeping track of the current maximum stock and its warehouse number.
   • Because of the condition “if there are multiple warehouses with the maximum value, output the smallest number,” we update the warehouse number only when a value strictly greater than the current maximum is found.
4. Output: Print the recorded warehouse number.

Complexity

• Time complexity: \(O(N + M)\)
  • Reading input takes \(O(N + M)\), processing instructions takes \(O(M)\), and finding the maximum takes \(O(N)\).
• Space complexity: \(O(N)\)
  • \(O(N)\) memory is used for the array holding each warehouse’s stock.

Implementation Notes

• Fast I/O: Since \(N, M\) are large, in Python it is faster to read all input at once using sys.stdin.read().split() rather than calling input() repeatedly, which reduces execution time.

• Range of values: Stock quantities \(P_i\) and transfer amounts \(W_j\) can be up to \(10^9\), so the final stock values can become very large. Python natively supports arbitrary-precision integers, so there is no need to worry about overflow.

• Index adjustment: The problem uses 1-indexed numbering (starting from 1), but program arrays are often 0-indexed (starting from 0), so be careful not to forget the correction using U-1 and V-1.

  Source Code

import sys

def solve():
    # 入力を一度に読み込み、空白で分割してトークンのリストを作成します
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    it = iter(input_data)
    
    # 倉庫の数 N と配送指示の数 M を取得します
    try:
        N = int(next(it))
        M = int(next(it))
    except StopIteration:
        return
    
    # 各倉庫の初期の商品数 P をリストに格納します
    # P[i] は倉庫 i+1 の商品数を表します
    P = [0] * N
    for i in range(N):
        P[i] = int(next(it))
        
    # M 件の配送指示を順番に処理します
    for _ in range(M):
        u = int(next(it))
        v = int(next(it))
        w = int(next(it))
        
        # 倉庫 U_j から W_j 個減らし、倉庫 V_j に W_j 個加えます
        # 倉庫番号は 1-indexed なので、インデックスを調整します
        P[u-1] -= w
        P[v-1] += w
        
    # すべての指示を実行した後の各倉庫の商品数から、最大値を特定します
    # 最大値が複数ある場合は、最も小さい倉庫番号を保持します
    max_stock = -1
    ans_warehouse = -1
    for i in range(N):
        if P[i] > max_stock:
            max_stock = P[i]
            ans_warehouse = i + 1
            
    # 結果を出力します
    sys.stdout.write(str(ans_warehouse) + '\n')

if __name__ == '__main__':
    solve()

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