А можно input 67-го теста?
Ошибка вполне понятна. Константный вектор сам по себе в вектор на преобразуется. Если хотите узнать в чем ошибка, укажите компилятор, который использует “у меня”.
Ваше определение графа просто убийственно. Зачем Вам вектор траля-ля указателей на вектор??? Храните в graph число i соответствующее arcs[i]. Дальше даже смотреть не стал, боюсь голова треснет. Пожалейте меня и переделайте.
67й тест является перемешанной копией одного из предыдущих тестов.
В силу не совсем ясных особенностей, почти все решения на 67м тесте работают в 12 раз медленнее, чем в таком же, но не перемешанном.
Причина, скорее всего, кроется в том, что, когда дуги добавляются push_back’ами в хаотичном порядке, они размещаются в памяти не самым удачным образом. В итоге кешпромахи дают ощутимый спад производительности.
Справится с 67м тестом можно, понизив константу или обойдя кешпромахи.
@Ivan_Ivanov пооптимизуруйте код, в частности, передачу параметров в функциях, и главное работу с памятью.
Функция поиска лексикографически минимального пути работает раз в 300 быстрее, чем функця поиска самих путей, и где-то в 180 раз быстрее, чем функция поиска максимальной пропускной способности пути, ускорить которые нет никакой возможности. Попытка резервировать память под дуги заранее, избавление от передачи аргументов в функции не дали никакого ускорения. За одну секунду я успеваю обработать только 28 дней из 100 на 67 тесте, возможности добиться более быстрой работы нет.
Откуда такие точные оценки? Как это измерялось?
Я так скажу, если мне покажется, что прохождение 67 теста требует каких-то особых знаний об устройстве памяти или еще что, то тест уберем. Но пока заявления в стиле “оптимизировать некуда” не принимаются, хотя бы потому что есть два принципиально разных правильных решения.
1)Я не очень понял, чем плохо мое представление графа? Каждая вершина это вектор из пар( смежная вершина, указатель на дугу(которая представлена вектором arcs)). 2)“У меня” - это MSVS. Что мне делать с этой ситуацией? Я не понимаю ошибки, я нигде не использую константных векторов.
Юра, константные вектора появляются при выведении типов шаблонов STL. Почему MS VC молчит, это вопрос к MS. А про указатели,я уже сказал. Они элементарно заменяются на индексы и с ними меньше мороки.
Юра, я пошел посмотреть снова на Ваш код и теперь хочу пару слов добавить. Вы же на STL ходили и задачу первую сделали. Компаратор должен удовлетворять концепции Compare. Вспоминается? Сигнатура функции-компаратора какая?
1 лайк
Для того, чтобы найти лексикографически минимальный путь, не обязательно вытягивать все дуги, по которым проходят пути максимальной пропускной способности.
Еще вектор, хранящий максимальные пропускные способности, является локальным в блоке цикла. На каждой итерации он разрушается и пересоздается (а в нем почти 10^5 элементов).
Сыграть на увеличение времени может многое. Но, но поиск сначала графа всех путей, а потом поиск пути в нем, наверноее, играет больше всего.
Можно закооментировать этот кусок и проверить: отработает ли меньше, чем за секунду или нет.
Графа всех путей наибольшей пропускной способности.
Спасибо, я нашёл, где у меня было излишнее.
Случайной перенумерацией вершин 67го теста можно добиться того, что даже самое хитро работающее решение будет отрабатывать около секунды. Часто больше секунды.
Все именно из-за кеш-промахов. Причем сортировки входных данными тут уже не помогают.
Прикладываю модифицированный 67й тест (только входные данные).067_modified.in.7z (306,6 КБ)
Challenge: придумать магическую обработку входных данных так, чтобы они с очень хорошей вероятностью удачно располагались в памяти. Либо предложить магический обход вершин, минимизирующий кол-во кеш-промахов, но приводящий к правильному ответу.
Этого теста НЕТ на ejudge и вряд ли он там появится. (это совсем издевательство будет)
Если решение не заходит по TL на ejudge, но укладывается на этом тесте - значит, надо еще подумать.
Чтобы оценить, на какое время работы надо ориентироваться на своей машине: посмотрите время работы 67го теста на ejudge и у себя. И отмасштабируйте 1 секунду.
Подтверждаю. Не появится.
Изи. Никаких отсечений и магической обработки входных данных.
В 1.8 раз дольше 67й теста, а 67й на ejudge у меня за 367мс проходит. 367*1.8 = 660 = accepted! =)
А можно, пожалуйста, input’ы 13-го и 54-го тестов?
Если это быстрейшее из тех решений, что я видел, то взлетает со скрипом:
прогонял его на стороне ejudge - 0.94сек 
Интересно, можно ли перемешать еще более неудачно?
Институт математики, механики и компьютерных наук ЮФУ, 2005–2021