10/04/2025 22:20:02

Рабочее место участника

Выбрать соревнование

Задачи

Послать решение

Результаты проверки

Статистика по задачам

Вопросы и ответы

Результаты соревнования

Задачи

2839. Зелье Гингемы

Ограничения: время – 600ms/1200ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Зелье колдуньи Гингемы может иметь много злобных эффектов, а общая сила зелья вычисляется как сумма сил всех отдельных эффектов. Каждый эффект может проявляться в зелье только 1 раз, поэтому при попытке добавления к зелью эффекта, которое оно уже имеет, сила зелья не изменится.

Каждый из эффектов может вызываться определенным ингредиентом, добавленным в зелье. Но (колдовство — сложная штука!) один и тот же ингредиент вызывает разные эффекты в зависимости от того, какой ингредиент добавлялся в зелье непосредственно перед ним. Хуже того, если положить в зелье непосредственно друг за другом несовместимые ингредиенты — оно испортится и полностью потеряет свою силу.

Помогите Гингеме сварить зелье с максимальной возможной силой из заданного набора ингредиентов.

В первой строке ввода находятся два целых числа: $N$ – количество ингредиентов ( $1<=N<=10^5$ ) и $M$ – количество возможных эффектов ( $0<=M<=10^5$ ). Затем следует $M$ строк по три натуральных числа в каждой, описывающих возможные эффекты:

$a_i$ - номер ингредиента ( $1<=a_i<=N$ ), вызывающего эффект;
$p_i$ – номер предшествующего ингредиента ( $1<=p_i<=N, p_i!=a_i$ ), который должен быть положен в зелье непосредственно перед $a_i$ -ым, чтобы эффект появился;
$s_i$ – сила эффекта ( $1<=s_i<=10^9$ ).

Например, строка "2 1 10" означает: если добавить в зелье ингредиент 2 сразу после ингредиента 1, то он вызовет эффект с силой 10. Обратите внимание, что пара "1 после 2" может быть несовместимой, даже если "2 после 1" приносит положительный эффект. Любые пары ингредиентов, кроме $M$ описанных, являются несовместимыми. Гарантируется, что добавление одного и того же ингредиента два раза подряд не приносит эффекта, а одна и та же пара ингредиентов встречается в описании не более 1 раза. Один и тот же ингредиент разрешается добавлять в зелье несколько раз. Первый добавленный в зелье ингредиент (тот, перед которым ничего не добавлялось) никогда не приносит самостоятельного эффекта.

Выведите одно целое число — максимальную силу зелья.

Пример ввода 1

Пример вывода 1

Пример ввода 2

10 0

Пример вывода 2

Пояснение к примеру 1: в первом случае можно добавлять ингредиенты в зелье в последовательности 1-2-3-2-3-5, общая сила эффектов 2+1+2+0+3=8. Эффект «3 после 2» добавляется только 1 раз, при первом появлении соответствующей пары. Компонент 7 не совместим ни с каким другим и его нельзя добавить в зелье, не испортив его.

Пояснение к примеру 2: все 10 ингредиентов несовместимы между собой. Из них нельзя сварить ни одного зелья с положительной силой.

29/03/2025	Открытые командные соревнования по спортивному программированию "PRIME TIME" (12)
29/03/2025	ЦОП: дорешивание Prime Time 2025 (проводит BOGAT) (E)