Overview

Given \(N\) warehouses, apply \(M\) delivery instructions (moving goods) all at once, then find the warehouse number with the most goods.

Analysis

Key Insight: Deliveries are applied “all at once”

The problem states that “the \(M\) delivery instructions are applied all at once, not sequentially.” This means the order in which we process each delivery instruction does not affect the result. The final number of goods in each warehouse can be calculated as follows:

\[\text{Final goods}_i = P_i + (\text{total goods coming into warehouse } i) - (\text{total goods leaving warehouse } i)\]

Is a naive approach sufficient?

Consider a naive method where we read each delivery instruction one by one, subtract \(W\) from the source warehouse, and add \(W\) to the destination warehouse. This operation takes \(O(1)\) per instruction and \(O(M)\) for all \(M\) instructions. Finally, finding the maximum among \(N\) warehouses takes \(O(N)\), but since \(N, M \leq 2 \times 10^5\), this is fast enough.

No special algorithm is needed for this problem — a straightforward simulation suffices.

Concrete Example

For example, with \(N = 3\), initial goods \(P = [10, 20, 30]\), and delivery instructions “warehouse 1 → warehouse 2: 5 items” and “warehouse 3 → warehouse 1: 15 items”:

• Warehouse 1: \(10 - 5 + 15 = 20\)
• Warehouse 2: \(20 + 5 = 25\)
• Warehouse 3: \(30 - 15 = 15\)

The warehouse with the most goods is warehouse 2 with 25 items, so the answer is 2.

Algorithm

1. Store the initial number of goods for each warehouse in array \(P\).
2. Read the \(M\) delivery instructions in order. For each instruction “move \(W_j\) items from warehouse \(U_j\) to warehouse \(V_j\)”:
   • \(P[U_j] \mathrel{-}= W_j\) (subtract outgoing goods)
   • \(P[V_j] \mathrel{+}= W_j\) (add incoming goods)
3. Scan array \(P\) and output the warehouse with the maximum value, choosing the smallest-numbered one if there are ties.

Complexity

• Time complexity: \(O(N + M)\)
  • \(O(N)\) for reading initial goods, \(O(M)\) for processing delivery instructions, \(O(N)\) for finding the maximum
• Space complexity: \(O(N)\)
  • Only the array holding the number of goods for each warehouse

Implementation Notes

• 1-indexed vs 0-indexed conversion: Warehouse numbers start from 1, but Python arrays start from 0, so you need to access them using U-1 or V-1.

• Integer overflow: Since \(P_i\) and \(W_j\) can be up to \(10^9\) and additions accumulate, the final values can become large. In Python, integer overflow does not occur, so this is not a problem, but in C++ etc., you need to use long long.

• Fast input: Since \(N, M\) can be up to \(2 \times 10^5\), in Python we speed things up by reading all input at once using sys.stdin.buffer.read().

• Multiple warehouses with the same maximum: By scanning from the beginning and taking the first position where the maximum is found, we naturally select “the smallest-numbered one.”

  Source Code

import sys

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    P = [int(input_data[idx + i]) for i in range(N)]
    idx += N
    for _ in range(M):
        U = int(input_data[idx]); idx += 1
        V = int(input_data[idx]); idx += 1
        W = int(input_data[idx]); idx += 1
        P[U - 1] -= W
        P[V - 1] += W
    
    max_val = P[0]
    max_idx = 0
    for i in range(1, N):
        if P[i] > max_val:
            max_val = P[i]
            max_idx = i
    print(max_idx + 1)

main()

---

This editorial was generated by claude4.6opus-thinking.