Що саме мінімізуємо. Козаків у кожному місті нескінченно багато, і всі мішки несуть одночасно. Тому загальний час — це не сума робіт, а найдовша окрема подорож. Задача формулюється так: розподілити мішки по бункерах з урахуванням місткостей так, щоб максимальна відстань «місто його бункер» була мінімальною.
Двійковий пошук за відповіддю. Зафіксуємо межу . Тоді кожне місто може користуватися лише тими бункерами, до яких відстань не перевищує , і питання стає суто транспортним: чи можна розвезти всі мішки, не перевищивши місткостей?
Перевірка — умова Голла, а не потік. Бункерів щонайбільше — це запрошення перебрати всі 2^{18} підмножин. Транспортна задача здійсненна тоді й лише тоді, коли для кожної підмножини бункерів
Тобто мішки, яким нікуди подітися, окрім , мають туди вміститися. Це дефектна форма умови Голла для транспортної задачі; запускати потік не треба.
Рахується це швидко. Для кожного міста визначаємо маску доступних бункерів і додаємо p_i у комірку цієї маски. Далі одним проходом «сум по підмножинах» (SOS-динаміка, \mathcal{O}(2^s \cdot s)) отримуємо для кожної сумарну пропозицію міст із маскою і порівнюємо з місткістю . Місто з p_i > 0 і порожньою маскою одразу робить непридатним.
Відстані. Потрібні відстані від міст до бункерів, а дороги односторонні. Тому будуємо обернений граф і запускаємо по одному Дейкстрі з кожного бункера — за s \le 18 запусків отримуємо всі потрібні відстані. На m \le 6\cdot10^5 ребрах це \mathcal{O}(s \cdot m \log n).
Двійковий пошук. Кандидатами на відповідь є лише самі значення відстаней (їх \le n \cdot s), тож сортуємо їх і шукаємо двійковим пошуком по індексу. Якщо навіть при нескінченному умова Голла порушується (сумарна місткість менша за кількість мішків або якесь місто взагалі не має шляху до бункера), виводимо .
Складність — \mathcal{O}\bigl(s\,m \log n + \log(ns)\cdot(n + 2^s s)\bigr). Мішків до 10^{14} сумарно, місткості до 10^9, відстані до 10^{14} — усе в -бітних.