dalbio

Эйлеров цикл существует в графе, только если входная степень каждой вершины равна ее выходной степени.

Эйлеров путь существует от вершины с выходной степенью на 1 больше входной степени до вершины у которой входная степень на 1 больше, чем выходная. (Если граф неориентированный, то путь от одной нечетной вершины до другой). При этом все остальные вершины должны быть сбалансированны.

Это элементарно доказать - путь в каждую вершину входит сколько-то раз и столько же раз выходит. Исключение - только начальная и конечная вершина, если они не совпадают.

Соответственно, вам надо подсчитать степени всех вершин, проверить что все хорошо (максимум одна с in==out+1 и одна с in==out-1) и запустить или от любой или от той, у которой исходящих ребер больше.

unordered_map может работать за линию в худшем случае. Это если происходит много коллизий. Стандартная реализация еще и дико медленная, через связные списки работает и часто использует тривиальные хеши (буквально, значение int берется за значение хеша). Подобрать смертельный тест для такого хэша совсем не сложно. Введите вашей программе на вход координаты деревьев i*8192 - если я правильно понимаю, unordered_map будет работать ооочень долго.

Можно избавиться от таких тривиальных коллизий, если реализовать свою хеш функцию. А там можно хоть (x * 239017l) % (1<<31) возвращать. И то, лучше будет.

Еще, чтобы избавиться от постоянных рехешированний можно добавить вот это:

len.reserve(1048576);
len.max_load_factor(0.25);

Говорят, что если заранее зарезервировать место и указать load_factor поменьше, то unordered_map будет раз в 10 быстрее.

Плюс, константа у unorderd_map выше - ибо надо хеши считать и перехешировать всю таблицу, если чисел становится много. Может, оно бы было быстрее для миллиона чисел, а не 100000, как у вас там.

Просто так примененная в лоб функция Гранди нисколько не быстрее обычных пометок "выигрышная"/"проигрышная" ситуация. Даже медленнее, потому что надо не просто смотреть, есть ли переход в выигрышную ситуацию, а надо смотреть в какие значения можно сделать переход и найти минимальное ими не покрытое.

Но она обладает замечательным свойством - если состояние игры можно разложить на несколько независимых игр и игорк в свой ход может сделать ход в любой из игр, то функция Гранди может быть подсчитана как xor значений для всех состояний. По умному это называется, что игра является суммой игр. В некоторых задачах это позволяет колоссально сократить простарнство состояний.

Один пример - игра Ним. Есть несколько кучек камней. За свой ход игрок может взять сколько угодно камней из любой кучки. Проигрывает тот, кому не останется камней. В простом переборе вам придется в качестве состояния хранить вектор количеств камней в каждой кучке. Но ведь тут стостяние очевидно раскладвается на под-игры: каждая кучка - своя отдельная игра. Причем, функция Гранди тут тривиальна - это просто количество камней. Вот и получается решение игры Ним - взять xor размеров всех кучек. Если не 0, то состояние выгрышное. Надо взять из какой-то кучки столько камней, чтобы получился xor, равный 0.

Еще пример - есть плитка шоколада. Игроки ее ломают вдоль клеток. За свой ход игрок может взять любой прямоугольный кусок и разломить его как-то вдоль клеток (если там более 1x1 клеток, конечно). Проигрывает тот, кто не сможет сделать ни одного хода. Опять же, при простом переборе пришлось бы хранить в состоянии размеры всех кусоков. Тут ОЧЕНЬ много вариантов. А с функцией Гранди - достаточно рассмотреть состояния вида "одна плитка размера n x m". После одного хода у вас будет 2 плитки, но меньшего размера. Вы уже знаете для них функцию гранди, XOR'ите их и получаете функцию для возможного перехода.

Попробуйте читать через scanf.

Я вижу, вы делаете через sync_with_stdio(0), но я не уверен, что это 100% помогает.

Потом, вместо set vis достаточно передавать в dfs предыдущую вершину и не ходить в нее.

А еше у вас ошибка, при делении ребра пополам нельзя делить пополам cnt*w. Если cnt четное, а w нечетное, вы потереяете округление. Надо пихать в кучу пару cnt, w, и брать максимальное cnt*ceil(w/2). И еще, вы пихаете в кучу цену ребра, помноженную на количество листьев по этому ребру и всем предыдущем в текущей вершине! Надо там не cur брать, а значение dfs.

И еще, оно скорее всего виснет из-за переполнения. При умножении cur*c.second может получиться отрицательное число, вы же int-ы перемножаете, и только потом к long long приводите.

Вы говорите, что пытаетесь брать числа, чтобы "портить" меньшие биты, но ведь это может быть не так.
Если у вас числа 4,4,4,4,5,6,1,1 - то выгодно брать именно 6, потому что оно сделает второй бит единицей, что никак невозможно сделать, взяв 5.
У вас неправильное решение задачи.

Правильное решение такое: Найдите самый старший бит, в котором нечетное количество единиц в массиве a.

Если таких нет - то ответ Draw. Потому что, если в каком-то разряде единиц четное количество, и x из них достанется первому игроку, то второму достанется 2k-x, что будет иметь ту же четность, что и x. А значит в этом разряде итоговые значения отличаться не могут вообще. Как числа не распределяй, даже если игроки могут делать разное количество ходов.

Теперь мы знаем, что в этом разряде различие точно будет. Потому что нельзя нечетное количество единиц распределить на 2 группы с одинаковой четностью. Победа определяется только этим разрядом, ведь он самый старший из различий. Теперь у нас есть 2k+1 чисел c 1 в этом разряде и n-2k-1 чисел с 0 в этом разряде. На биты дальше смотреть не надо - кто возьмет нечетное количество чисел из 2*k+1 - тот победил.

Т.е. вам дальше надо решить совсем простую задачу: Дана пара чисел (i,j), i - нечетно, есть i нужных объектов и j ненужных, игроки по-очереди берут объекты. Кто возьмет нечетное количество нужных объектов - тот и победил.

Тут для вывода решения можно написать динамическое программирование, которое для пары (i,j) - будет говорить, сможет ли игрок взять четное/нечетное количество нужных чисел, если их i, и еще есть j ненужных. При расчете перебирайте варианты, какой из типов объектов берется и смотрите, а сможет ли оппонент вам четность испортить на меньшей задаче.

Дальше надо посмотреть на паттерн на маленьких числах и составить решение, потому что вся эта динамика у вас по времени не зайдет для данных ограничений.

Мне лень решать дальше задачу, но похоже, что при i=1 ответ - WIN, при i>0 - ответ Win, если i+j=n - четно. Иначе - Lose.

Тут мало выбирать только первое число и гнать обычный бинарный поиск. Важное ограничение - вы не можете использовать один и тот же цвет дважды. Есть еще спецэффект, что случаи c=n-1 и с=n можно разделить только перекрасившисть с 1 на n или наоборот. Т.е. вы не имеете права краситься в 1 или n-1, только если не знаете точно, что C меньше n или что С одно из двух крайних значений.

Нужно придумать какой-то паттерн, как компактно расположить все запросы в промежутке от 1 до n без повторений.

Это классическая задача о рюкзаке.

Можно составить такое ДП: F(c, k) - максимальное количество страниц, которые можно набрать из первых k книг общей стоимостью ровно c.

База: F(0,0) = 0, F(0,*) = F(*,0) = -infinity.
Пересчет:

F(c, k) = max(F(c-cost[k], k-1) + pages[k], F(c,k-1))

Это ДП приведено в википедии, например. Ответ - максимум по всем c F(c,k).

Есть одна хитрость при реализации - можно обойтись только одной строкой этой матрицы, если вам не нужно восстанавливать весь набор книг в ответе, а только его лучшее значение (только надо поменять параметры местами - строка размером с максимальную цену). Это сократит потребление памяти в K раз, если у вас K книг. На скорость работы решения это не влияет.

Сначала реализуйте все дп на матрице снизу вверх, двумя циклами.
Теперь, если вы будете гнать внутренний цикл с конца к началу, то вам не понадобится смотреть на уже переписанные на текущей итерации внешнего цикла значения, и можно забить на второй параметр ДП и просто переписывать строку на месте.

long long matr[1001][1001] - это будет 8016008 байт, 7.645МБ.
Стандартный размер стека в MS Visual Studio задан в 1МБ. Естественно, при объявлении настолько большого массива ты сразу получишь Stack Overflow.

Выходов из данной ситуации несколько.
Выход первый - подойти к вопросу рассудительно. Тебе точно нужен именно статический массив в 8МБ именно на стеке? Я думаю что нет. Я думаю что тебе нужен std::vector, в котором ты сможешь легко разместить все 1002001 элементов. На самом деле и двумерность массива тебе тоже не очень нужна, т.к. на самом деле она тебя сейчас только запутывает. Через простую функцию от двух аргументов можно легко перейти от двух индексов к индексу в линейном массиве.

Выход второй - вынести свой статический массив за пределы контекста функции. Это можно сделать, объявив этот массив как static или объявив его в глобальной области видимости.

Выход третий, которым я советую не пользоваться без однозначного понимания своих действий.
Можно изменить размер стека через настройки линкера.
В свойствах проекта: Configuration Properties -> Linker -> System:
Stack Reserve Size - значение в байтах, это максимальный размер стека для потока. Его можно изменить хоть до 32МБ и больше.

Подвох с этим значением в том, что потоков у твоего приложения не один даже если само твое приложение является однопоточным. Вместе с твоим главным потоком работает еще несколько служебных. Их стек тоже будет расширен. Это все приводит к увеличению потребления памяти.
Обычно размер стека по умолчанию не трогают или сжимают до 64КБ, т.к. большинству потоков этого более чем достаточно. А вот для требовательных потоков, обычно, отдельно расширяют стек до требуемых размеров в момент создания потока.
Таким образом достигается контроль памяти. Даже сегодня бывают случаи, когда ее бывает мало.

Посмотрите ,на какой строчке останавливается отладка

Например, vector<vector<pair<int, int>>>, где каждый внутренний vector<pair<int, int>> содержит рёбра, ведущие из вершины с соответствующим индексом, а каждая pair<int, int> - это пункт назначения и вес ребра.

Использовать свойство

Есть решение, но оно на плохих тестах, если не повезет, не влезет в лимит.
Чтобы вам повезло, можно "перемешать" входные данные случайным образом. Заведите случайную перестановку. Далее внизу я про нее как бы забуду, но когда я говорю спросить про элементы i и j вы должны справшивать про p[i] и p[j]. Как только вы найдете, что 0 в p[k] - про эту случайную перестановку можно забыть и далее использовать элемент p[k] для востановления перестановки.

Спросите про элементы 0 и 1. Запомните a[0] | a[1].

Вот у вас есть 2 элемента каких-то, вы знаете их позиции и a[i]|a[j]. Мы будет добавлять к ним элементы 2..n-1 по одному, все время выбрасывая один или несколько, в которых нуля точно нет.

Вот есть у вас элеметы x, y и вы знаете a=x|y. возьмем новый элемент z и спросим b=y|z.

Мог ли 0 быть в x? тогда бы a = x|y=0|y = y. Т.е. предыдущее значение a должно вкладываться в новое b как множество единиц. Аналогичный критерий для возможности z быть нулем - b вкладывается в a.

Eсть 4 взаимоисключающих варианта, как множества бит a и b соотносятся:
1) a целиком вкладывается в b, или a|b == b, a != b, например 5 вкладывается в 7.
2) b целиком вкладывается в a, или a|b == a, a != b
3) a == b
4) ничего из выше перечисленного, например, 3 и 6.

Мы уже становили, что x может быть 0 только в случаях 1) и 3). z может быть нулем только в случаях 2) и 3).

В каких случаях может быть нулем y? только в 1), 2) и 4)

Теперь алгоритм, если выпал случай 1), то мы выбрасываем z. При этом значение текущего OR уменьшилось как множество.

Если выпал случай 2), то мы выбрасываем x. При этом значение текущего OR уменьшилось как множество.

Если выпал вариант 3), то мы выбрасываем y и нам придется спросить x|z, ведь нам надо знать OR оставшихся элеметов. Это плохо тем, что мы спросили 2 раза, рассморев один новый элемент. В неудачном случае мы бы задали 2n вопросов только ища 0 и у нас не осталось бы квоты на восстановление самой перестановки.

Но тут есть 2 подварианта. 3а) Если значение x|z стало меньше, как множество, то ок. 3б) Но оно еще могло бы остаться таким же, т.е. x|y=y|z=x|z. Но в этом случае, по аналогичным рассуждениям нуля не может быть нигде среди этих трех элементов! А значит мы можем выкинуть и их все, избавившись от двух элементов за два вопроса.

Если выпал вариант 4), то мы выбрасываем x или z.

Таким образом задав от n до 2n (в самом неудачном случае) мы получаем в конце 2 элемента в одном из которых точно 0, а второй - a.

Чтобы восстановить кто из двух оставшихся элементов кто: по ходу отсеивания, задавая любой вопрос запоминайте для какой пары чисел вы видели нулевой бит в каждом разряде. (Т.е. спросили про i|j получили ответ 5. Тут второй бит 0, значит запомнили, что i|j дает 0 в бите 2. И поддерживайте массив для всех разрядов).
Если вам хоть сколько-нибудь повезет. вы наберете достаточно таких примеров.

Теперь пройдитесь по всем примерам, что вы ранее видели и выберите тот, который имел 0 в разряде, где у a стоит 1. пусть это были элементы i и j. Теперь спросите x|i. Если и там этот разряд 0, то x=0, иначе у=0.

Тут почти нарисовался строго убывающий инвариант - размер множетсва бит в OR для текущих кандидатов, но пункт 3б) его ломает, ведь мы получаем 2 новых элемента и множество может стать любым. Но случайный порядок вопросов должен сделать этот вариант маловаероятным. У вас запас примерно 150 впоросов на максимальном тесте. Возможно тут можно придумать какую-то строгую схему, где какой-то инвариант строго убывает на лишних вопросах и может убывать не более 100 раз.

Это невозможно.
Пусть у нас есть массив, состоящий НЕ ЦЕЛИКОМ из нулей и содержащий хоть один ноль.
Возьмём любой ненулевой элемент a и про-XOR’им с ним все элементы массива.
Ноль переместился в другое место, а результаты нашей операции a[i] xor a[j] не изменились.
Получается, что первый массив неотличим от второго, и нули в них в разных местах.

Например: массив 0 1 2 3 неотличим от массива 1 0 3 2.
0 xor 1 = 1 … 1 xor 0 = 1
0 xor 2 = 2 … 1 xor 3 = 2
0 xor 3 = 3 … 1 xor 2 = 3
1 xor 2 = 3 … 0 xor 3 = 3
1 xor 3 = 2 … 0 xor 2 = 2
2 xor 3 = 1 … 3 xor 2 = 1
Ну а 0 xor 0, 1 xor 1, 2 xor 2 и 3 xor 3 всегда были нулями.

------------------

В версии с OR — берём a[0] or a[i], поддерживая AND этих сумм и подсчитывая, сколько раз этот самый AND среди наших сумм встречается.
1) Если числа, превышающие AND, встречаются столько раз, сколько [ну, подсчитайте, сколько чисел от 0 до N−1 будут иметь все эти биты] — отбросим наше 0-е число, а также проверенные числа, чья сумма НЕ совпадает с AND, и начнём сначала.
ПРИМЕР: 2 3 4 0 1
2 or 3 = 5, AND=5
2 or 4 = 6, AND=2 — бит 2 тут будут иметь только 2 и 3, отбрасываем 2, 3 и 4.

Если AND встречается 2^k−1 раз (k — кол-во битов в AND), оставим ТОЛЬКО ЭТИ случаи и снова начнём сначала.
ПРИМЕР: 2 1 0 3
2 OR 1 = 3, AND=3
2 OR 0 = 2, AND=2
2^k−1=1, и нам хватает одной встречи числа 2 — оставляем 2 и 0.

Остались три числа — действуем по стандартному алгоритму.
Осталось одно число — оно 0.
Остались два числа — одно 0, другое некий бит. Мы должны найти число, этого бита не имеющее. Снова проходим по результату предыдущего обхода, суммируя сначала с одним, потом с другим. Видим разницу — понятно, где 0, а где бит.

const нужен потому, что если компаратор будет что-то в контейнере менять, у контейнера явно поедет крыша. Профессионалы вешают const (а еще лучше - constexpr) на любую сущность, которая не должна меняться по логике алгоритма.

Ссылки передаются по той простой причине, что это избавляет от вызова конструктора копирования и деструктора, что может быть крайне критично для некоторых тяжелых объектов, или же будет блокировать компиляцию с кучей ошибок, если объект не позволяет себя копировать