Страны и города
Вы решили задачу. Теперь можно сравнить подходы.
Строим обратное соответствие от города к стране.
Авторский разбор для локальной версии на основе условия задачи. Это не выгрузка чужих посылок и не официальное решение исходного сайта.
Ваше принятое решение
Рекомендуемое решение: Индекс городов
Каждый город становится ключом словаря, поэтому ответ находится без повторного обхода стран.
n = int(input())
country_of = {}
for _ in range(n):
country, *cities = input().split()
for city in cities:
country_of[city] = country
for _ in range(int(input())):
print(country_of[input()])
Время: Ожидаемое O(C + Q), C — число городов, Q — запросов (без учёта длины строк). Память: O(C) записей и памяти для названий.
Другой способ: Множества городов по странам
Сохраняем исходное направление связи и проверяем принадлежность города каждой стране.
n = int(input())
countries = []
for _ in range(n):
name, *cities = input().split()
countries.append((name, set(cities)))
for _ in range(int(input())):
city = input()
for name, cities in countries:
if city in cities:
print(name)
break
Время: Ожидаемое O(C + Qn). Память: O(C + n) записей и названий.
На что обратить внимание
- Название страны — первый элемент строки, остальные элементы — города.
Рекомендация учитывает сложность и читаемость для этой задачи. Единственного самого быстрого решения для всех размеров входа и всех компьютеров может не быть.