Overview

For each day, from the ingredients available for purchase, select at least one vegetable and at least one meat, and find the minimum total price. If no valid combination exists, output \(-1\).

Analysis

In this problem, each day has a restricted set of “ingredients available that day,” and we need to select a total of 2 types: “1 vegetable + 1 meat.” The goal is to minimize the total price.

Issues with a Naive Approach

A naive approach would be to try all pairs from the “available ingredient list” each day, but this costs up to \(O(K_j^2)\), and becomes extremely slow in the worst case when \(K_j\) approaches \(N\) (potentially \(O(MN^2)\) overall). This cannot handle the constraints \(N, M \sim 2 \times 10^5\).

Another approach would be to sort each day and find the minimum vegetable and meat, but this is also inefficient when the number of days is large.

Solution: Preprocessing and Maintaining Minimums

The key observation is that “on any given day, all we ultimately need is the minimum vegetable price and the minimum meat price among the ingredients available that day.”

Therefore, it suffices to classify each ingredient in advance (vegetable or meat), and for each day’s processing, scan the “available ingredient list” while updating the minimum vegetable price and meat price within it.

Algorithm

1. First, read in the prices and types of all ingredients.
2. For each day, do the following:
   • Manage the set of ingredient IDs available for purchase that day.
   • Look at each ingredient in the set and update the minimum price according to its type (vegetable or meat).
   • Finally, if minimums for both types were found, record their sum; otherwise, record \(-1\).
3. Output all results.

With this method, each day can be processed in linear time with respect to the “number of available ingredients \(K_j\).”

Complexity

• Time complexity: \(O(N + \sum_{j=1}^{M} K_j)\)
  (Reading each ingredient is \(O(N)\), and scanning available ingredients each day is \(O(\sum K_j)\))
• Space complexity: \(O(N + \max K_j)\)
  (Array to store ingredient information, and a set to hold available ingredients for each day)

Implementation Notes

• sys.stdin.read is used for fast input reading.

• Since each ingredient’s type (\(T_i\)) is either 0 (vegetable) or 1 (meat), classification can be done easily using a list or array.

• Since the “available ingredients” each day contain no duplicates, managing them with a set allows for efficient lookup.

• Initializing minimum values with float('inf') is a common and safe practice.

  Source Code

import sys
import heapq
from collections import defaultdict

input = sys.stdin.read

def main():
    data = input().split()
    idx = 0
    
    N = int(data[idx])
    idx += 1
    M = int(data[idx])
    idx += 1
    
    # 食材の価格と種類を読み込む
    prices = [0] * (N + 1)
    types = [0] * (N + 1)
    
    for i in range(1, N + 1):
        prices[i] = int(data[idx])
        idx += 1
        types[i] = int(data[idx])
        idx += 1
    
    # 野菜と肉類の最小価格を保持するリスト
    veg_heap = []   # (price, id)
    meat_heap = []  # (price, id)
    
    # 全食材に対して最小ヒープを構築
    for i in range(1, N + 1):
        if types[i] == 0:
            heapq.heappush(veg_heap, (prices[i], i))
        else:
            heapq.heappush(meat_heap, (prices[i], i))
    
    # 各日について処理
    results = []
    for _ in range(M):
        K = int(data[idx])
        idx += 1
        available = set()
        for __ in range(K):
            s = int(data[idx])
            idx += 1
            available.add(s)
        
        # 利用可能な食材の中で最小の野菜と肉を求める
        min_veg = float('inf')
        min_meat = float('inf')
        
        for item_id in available:
            if types[item_id] == 0:
                if prices[item_id] < min_veg:
                    min_veg = prices[item_id]
            else:
                if prices[item_id] < min_meat:
                    min_meat = prices[item_id]
        
        if min_veg == float('inf') or min_meat == float('inf'):
            results.append("-1")
        else:
            results.append(str(min_veg + min_meat))
    
    print("\n".join(results))

if __name__ == "__main__":
    main()

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