Overview

There are \(N\) warehouses, each with an initial stock. Given \(M\) delivery instructions that move goods between warehouses, find the number of the warehouse with the most stock at the end.

Analysis

In this problem, if we naively update the stock for each delivery instruction, in the worst case we would modify each warehouse’s stock \(M\) times, resulting in excessive computation. Additionally, there may be multiple transfers between the same pair of warehouses.

However, the key insight is that we only need “the final stock of each warehouse”, so there is no need to actually simulate the movement of goods. Instead, it is sufficient to record “how many items came in and how many went out” for each warehouse.

To manage these differences, we maintain a net change (diff) for each warehouse. For example, when moving \(w\) items from warehouse \(u\) to warehouse \(v\): - Warehouse \(u\)’s stock decreases by \(w\) → diff[u] -= w - Warehouse \(v\)’s stock increases by \(w\) → diff[v] += w

After processing all delivery instructions, we add the differences to the initial stocks to compute the final stocks, and output the number of the warehouse with the maximum value.

Algorithm

1. Read the initial stock of each warehouse as a list \(P\).
2. For each delivery instruction \(U_j, V_j, W_j\):
   • Add \(-W_j\) to the diff of warehouse \(U_j - 1\) (0-indexed)
   • Add \(+W_j\) to the diff of warehouse \(V_j - 1\)
3. Compute the final stock of each warehouse as \(P_i + \text{diff}[i]\).
4. Among the warehouses with the maximum final stock, select and output the one with the smallest number.

Complexity

• Time complexity: \(O(N + M)\) (Reading initial stocks \(O(N)\), processing delivery instructions \(O(M)\), computing final stocks and finding the maximum \(O(N)\))
• Space complexity: \(O(N)\) (Size of the initial stock and diff arrays)

Implementation Notes

• Warehouse numbers are given as 1-indexed in the input, so when handling them internally, they need to be converted to 0-indexed (subtract 1).

• By applying all differences in bulk and computing the final stocks only once at the end, we can process everything efficiently.

• When multiple warehouses share the maximum value, note that you must select the one with the smallest number.

  Source Code

import sys
from collections import defaultdict

input = sys.stdin.read

def main():
    data = input().split()
    N = int(data[0])
    M = int(data[1])
    
    P = [int(data[i + 2]) for i in range(N)]
    
    # 差分を記録するための配列（または辞書）
    diff = [0] * N
    
    index = 2 + N
    for _ in range(M):
        u = int(data[index]) - 1
        v = int(data[index + 1]) - 1
        w = int(data[index + 2])
        diff[u] -= w
        diff[v] += w
        index += 3
    
    # 各倉庫の最終的な商品数を計算
    final_counts = [P[i] + diff[i] for i in range(N)]
    
    # 最大値を持つ最初のインデックスを見つける
    max_count = final_counts[0]
    max_index = 0
    for i in range(1, N):
        if final_counts[i] > max_count:
            max_count = final_counts[i]
            max_index = i
    
    print(max_index + 1)

if __name__ == "__main__":
    main()

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