Когда я был маленьким ребёнком я многому научился (через сайт) у e-maxx.(Orz).

Вчасности там есть пост про Нахождение кратчайших путей от заданной вершины до всех остальных вершин алгоритмом Дейкстры для разреженных графов . Там сказано что priority_queue реализован через кучи, и имеет меньшую константу чем set который базируеться на КЧ-деревьях. Обьяснение внятное.

Я вернулся в длинного перерыва в СП и посмотрел на недавний Educational Codeforces Round 102 (рейтинговый для Див. 2) ради разогрева. Там была милая 1473E - Минимальный путь написання Neon которая требовала Алгоритм Дейксры. Я использовал priority_queue из моей заготовки 105061903 и получил ТЛ 61. Я чертыхнулся и начал оптимизировать. В результате я попробоваь решение на set-ах и получил АС 105066945. Вот изменения:

Почему Дейкстра на set-ах работает быстрее чем дейкста на priority_queue?

Здравствуйте,

Нужно было решить Алгоритм Укконена, что-бы решить эту задачу. По сему я искал и нашёл это, и это, и это, и это, решил что я понял теорию и приступил к реализации этой задачи.

Пытался реализовать это читабельно и протестировать немного и получил TL после оптимизировал и получил TL уже с этим, посему переписал код и всё ещё получаю TL и мой отпуск подходит к концу.

Кто-то может, пожалуйста, подсказать что же я упускаю (вроде бы, главное отличит от e-maxx-овской реализации то что я направляю суффиксные ссылки на следующем шагу, а не по требованию.

Спасибо и kiitos

This draft is 4 years old, so its time to post it, especially, since I found a bug in the code.

I just returned to violet and decided it is time to increase my contribution before next div 1 contest makes me blue again. had bad luck to learn binary search from informatics.mccme.ru (I think they rewrote article from that time but the irreversible damage was done and even after explaining tricks by my friends AndrewB330 and nagibator I still can not write binary search without bugs). And I was searching for easy tricks to use lower and upper bound functions of the STL library (yes I am talking about C++ only) to solve binary search problems. Anyway, you usually need to find the first element satisfying or not satisfying some conditions. So you can easily implement your "Iterator" class with difference, prefix increment, increment, not equal operator and dereference operator:

struct BinarySearchIterator : public iterator<random_access_iterator_tag, bool>
{
  long long value;

  typename iterator_traits<BinarySearchIterator>::difference_type operator - (const BinarySearchIterator &it) const { return value - it.value; }

  BinarySearchIterator& operator ++() { return *this += 1; }

  BinarySearchIterator& operator --() { return *this += -1; } // msys

  BinarySearchIterator& operator +=(typename iterator_traits<BinarySearchIterator>::difference_type n) { value += n; return *this;}

  bool operator != (const BinarySearchIterator &it) const { return value != it.value; }

  bool operator*() const {
    /* code here */
    return true;
  }
};

Since I wrote this post, Python has entered our lives. And those who use it for CP probably aware that one of the rare things from STL which exists in Python is the bisect module with bisect_left (equivalent to lower_bound) and bisect_right (equivalent to upper_bound). So we can abuse it to do binary search as well:

class BinarySearchCollection(object):
    def __init__(self, length=None):
        self.__length = length

    def __len__(self):
        return self.__length

    def __getitem__(self, item):
        raise NotImplementedError()

List of problems:

• 1251D - Salary Changing

• Blindfolded Bullseye

• New Elements: Part 2

Enjoy.

I suppose as a person with rating terribly going down this post will receive plenty downvotes, but still.

I suppose anyone, who used hacking with generator (and considering limit on file size for handmade tests, when you are hacking for TL another ways are impossible), hates messages like "Invalid input Unexpected character #13, but ' ' expected". Personally I receive them every time, and considering pending time... In other words it almost impossible to hack someone with generator (for me, do you have any tricks?)

Здравствуйте все! Вопрос вознпик, во время решения 100783D - Book Club. В ту ночь когда мы прочитали её, моей первой мыслью был максимальный поток в единичной сети с ребрами из источника во все А, из А в B, из всех B в сток должен быть равен к-ву ч-к. Начали искать алгоритм который подходит к ограничениям и нашли что Диниц когда его использовать для максимального паросочетания в двудольном графе работает за O(sqrt(V)E). (Вау подходит, ведь E<=N итого O(N^1.5)). Ок, реализовал я Диница почти как e-maxx и моя реализация упала на 13-ом тесте с TL.

На это AndrewB330 спросил, почему я не написал Куна, я подумав об этом согласился что O(N^2) вообще нормально подходит и получил свой AC.

Вопрос в том, что я такого страшного сделал (или не сделал) в Динице, что он не сработал как ожидаемо?

Премного благодарствую :)

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

Вопрос: кто-то может мне посоветовать задачу связанную с поиском Эйлерового цикла?

Зарание спасибо.