%s + "А я спать."

Ой как мы сочувствуем:) Вариант пропустить Facebook HC рассматривался?

Туда вроде ради контестов и ездят:) Ловите два)

Наверное, тут.

Их нельзя прочитать, если не прошел :(

md5: c8d468eb0d7c0d762071e74b92c8e2ef

Твой инпут прерывается на 17 тесте...

Элементы растут в среднем на 1. Зафиксируем начало отрезка и будем идти вправо, считая элементы которые еще не встречались, где-то через 100000 элементов новые будут встречаться периодически, то есть если среди N позиций 1-ая 4-ая и 9-ая была новой, то в следующих N на этих позициях тоже будут стоять новые числа. Кроме того если сдвинуть начало отрезка на N в любую сторону, то "новые" элементы тоже сдвинутся. Получается, что достаточно перебрать начало отрезка от 0 до N - 1, посчитать где должен быть его конец x, он на промежутке

Unable to parse markup [type=CF_TEX]

Не успел докодить. решение такое. Пусть мы знаем отрезок [a, b]. Тогда посчитаем в нем количество различных чисел. Для начала разобьем этот отрезок на N подпоследовотельностей, возможно, некоторые будут пустые, такие что в каждой из них у нас индексы элементов сравнимы по модулю N. Получили N таких подпоследовательностей. В каждой из них мы можем легко найти первый и последний элемент. Теперь давайте пробежимся по каждой из таких последовательнстей. Мы можем узнать остаток от деления на N первого элемента в каждой из них ( а каждая такая последовательность — это арифметическая прогрессия с разностью N). Тогда, если мы запомним для каждого rem какие последовательности были, то есть первый член и последний, то мы тогда получим что у нас для каждого rem есть набор отрезков ( вида rem + xN, rem + yN, где x, y — нам уже известны). Тогда посчитаем их длину их пересечения. Это будет число различных чисел для данного остатка. Проитерировав по всем остаткам, получим общее число различных числе для отрезка [a,b]. Теперь давайте решать исходную задачу. Перебираем индекс a = 0, ... , N — 1 Дихотомией перебираем индекс b. пусть мы нашли, что нам подходит [a, b]. Тогда понятно, что и [a, b + delta] подходит, а также будет подходить отрезок [a + N, b + N]. Тогда мы можем посчитать число валидных отрезков. начинающихся от этого элемента. Посчитаем общее число валидных и выведем ответ.

В первой оказывается можно не убирать рёбра между неважными городами. Остальные убираем чтобы было дерево, поэтому ответ вычисляется из кол-ва рёбер, кол-ва вершин, кол-ва компонент связности, и тому же самому но только по неважным городам.

В первой можно и дфсить из каждой хорошей вершины, и если мы нашли какое-то ребро, ведущее в нее, то удалим его.

Во второй, рассмотрим такое бинарное дерево, терминальные вершины — это вершины, которые пока не боссы и не подчиненные (компоненты размера 1). При появлении связи (u, v) найдем каким компонентам принадлежат вершины u, v — пусть это c1, c2, тогда найдем в дереве узлы, соответсвующие с1 и с2, создадим новую вершину, которая будет иметь два сына — узел для c1, для c2, т.е. теперь новая вершина соотвествует компоненте c1+c2. После это построения можно сделать динамику F(i,j) — минимальная высота дерева с корнем в i с учетом того что кол-во сыновей (характеристика, которая ограничивается D) должно быть <= i.

Я в первой использовал систему непересекающихся множеств... Сначала объединял все множества рёбрами, на концах которых нет важных городов, потом добавлял оставшиеся дороги. Когда добавлял очередную дорогу, хотя бы на одном конце которой есть важный город, считал количество попыток объединений множеств с "самим собой"

Немного другое решение второй. Будем по очереди объединять компании и для каждой хранить список людей, которые могут быть директорами. Для каждого из таких кандидатов в директора храним минимальный уровень который при нем достигается и количество непосредственных подчиненных (тут оно не зависит от способов объединения). Соответсвенно, при сливании компаний эти значения легко пересчитываются. Чтобы понимать кто в какой комании я, недолго думая, сделал СНМ. Трудоемкость такого решения оценить, правда, сложновато, но, вроде как, это что-то около О(ND). По крайней мере даже на питоне работает весьма шустро, да и пишется быстро.

Поздравляю :) Сам тоже доволен, как слон, до разморозки был 161 :)

Что-то я как-то... Проснулся даже

Инпут где взять? Или свой?

P.S. И да, там теперь можно скачать решение чьё угодно, можно взять любое подходящее и прогнать на своих тестах