Codeforces Round 728 (Div. 1) |
---|
Закончено |
Обратите внимание на необычное ограничение по памяти.
Есть $$$n$$$ поваров, пронумерованных $$$1, 2, \ldots, n$$$, которые готовят блюда для короля. Повар $$$i$$$ обладает мастерством $$$i$$$ и первоначально приготовил блюдо вкусности $$$a_i$$$, где $$$|a_i| \leq i$$$. У каждого повара есть список поваров, блюда которых он может копировать. Чтобы не допускать распространение плохих привычек, король гарантирует, что повар $$$i$$$ может копировать только у поваров с более высоким мастерством.
Повара работают над своими блюдами в течение нескольких дней. Каждый день работа над блюдом разбивается на два этапа.
Чтобы угодить королю, каждый повар стремятся максимизировать вкусность своего блюда.
Наконец, вам заданы $$$q$$$ запросов. Каждый запрос одно из двух видов:
Обратите внимание, что запросы типа $$$1$$$ не зависят от других запросов. Точнее говоря, каждый запрос типа $$$1$$$ — это только возможный сценарий и он не меняет вкусности $$$a_i$$$ для запросов далее. При этом запросы типа $$$2$$$ накапливаются, но меняют только первоначальные значения $$$a_i$$$ блюд. В примечании представлены примеры запросов.
В первой строке задано одно целое число $$$n$$$ ($$$1 \le n \le 300$$$) — количество поваров.
Во второй строке заданы $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$-i \le a_i \le i$$$).
Каждая из следующих $$$n$$$ строк начинается с целого числа $$$c_i$$$ ($$$0 \le c_i < n$$$), означающего количество поваров, у которых $$$i$$$-й повар может копировать блюда. Далее за ним следует $$$c_i$$$ различных числа $$$d$$$ ($$$i < d \le n$$$), обозначающих, что повар $$$i$$$ может копировать у повара $$$d$$$ каждый день во время $$$2$$$-го этапа.
В следующей строке задано одно целое число $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$) — количество запросов.
Каждая из следующих $$$q$$$ строк содержит запрос одного из двух видов:
Гарантируется, что есть хотя бы один запрос первого вида.
Для каждого запроса первого вида выведите одно число — ответ на этот запрос.
5 1 0 -2 -2 4 4 2 3 4 5 1 3 1 4 1 5 0 7 1 1 1 5 2 4 3 1 1 1 5 2 3 2 1 2 2 4 2 5 1 1 981 4 5
57 71 316 278497818
Ниже показаны множества поваров, у которых может копировать каждый из поваров в примере.
Далее следует описание первого примера.
Для первого запроса вида $$$1$$$ первоначальные значения вкусностей равны $$$[1, 0, -2, -2, 4]$$$.
Значения вкусностей после каждого этапа в первый день:
Таким образом, ответ на $$$1$$$-й запрос равен $$$21 + 0 - 2 + 18 + 20 = 57$$$.
Для $$$5$$$-го запроса ($$$3$$$-й вида $$$1$$$), первоначальные значения вкусностей теперь равны $$$[1, 0, 0, 1, 4]$$$.
День 1
День 2
Таким образом, ответ на $$$5$$$-й запрос равен $$$12+108+196=316$$$.
Можно показать, что на каждом описанном шаге все повара действовали оптимально.
Название |
---|