Overview

Given the initial stock of each warehouse and shipping instructions between warehouses, the problem asks to find the warehouse number with the maximum stock after all shipping instructions are applied simultaneously.

Analysis

The key point of this problem is that the shipping instructions are “applied all at once, not sequentially.” In other words, there is no need to process each shipping instruction in order, and the final stock of each warehouse can be calculated as follows:

• Final stock of each warehouse = Initial stock + (total quantity of goods coming into that warehouse) - (total quantity of goods going out of that warehouse)

Since each shipping instruction is simply in the form “move W items from warehouse U to warehouse V,” for each warehouse: - Total quantity of outgoing goods: the sum of W for all shipping instructions where that warehouse is the source - Total quantity of incoming goods: the sum of W for all shipping instructions where that warehouse is the destination

From this observation, we can see that by subtracting W from the source warehouse and adding W to the destination warehouse for each shipping instruction, we can compute the final stock quantities.

Algorithm

1. Store the initial stock of each warehouse in array P
2. For each shipping instruction:
   • Subtract W from the source warehouse U
   • Add W to the destination warehouse V
3. Find the warehouse number with the maximum final stock (in case of ties, select the smallest number)

Complexity

• Time complexity: \(O(N + M)\)
  • \(O(N)\) for reading initial stocks
  • \(O(M)\) for processing shipping instructions
  • \(O(N)\) for finding the maximum
• Space complexity: \(O(N)\)
  • The array storing stock quantities has size \(N\)

Implementation Notes

• When processing shipping instructions, warehouse numbers are given as 1-indexed, so they need to be converted to 0-indexed

• Since it is guaranteed that the stock of each warehouse will be non-negative after all shipping instructions are processed, there is no need to handle negative values

• When searching for the maximum, to select the smallest number in case of ties, a simple loop that only updates when a strictly larger value is found is sufficient

  Source Code

def main():
    import sys
    data = sys.stdin.read().split()
    idx = 0
    N = int(data[idx]); M = int(data[idx+1]); idx += 2
    P = list(map(int, data[idx:idx+N]))
    idx += N
    
    for _ in range(M):
        u = int(data[idx]); v = int(data[idx+1]); w = int(data[idx+2]); idx += 3
        u -= 1
        v -= 1
        P[u] -= w
        P[v] += w
        
    max_val = -1
    ans = -1
    for i in range(N):
        if P[i] > max_val:
            max_val = P[i]
            ans = i + 1
            
    print(ans)

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.