| 1 Филонич Владислав Александрович, 15 января 2025 г. 5:35:42 |
| Тест 6 - когда несколько дорог ведут в одну вершину.
|
|
|
| 2 Миролим, 22 ноября 2024 г. 9:24:23 |
| #include <iostream> using namespace std; int main(){ long long a1, a2, a3, a4, n; cin>>a1>>a2>>a3>>a4; n=min(a1,a2)+min(a3,a4); long long L=0, R=1.5e9, a; while(L!=R){ a=(L+R+1)/2; if(a*a<=n) L=a; else R=a-1; } cout<<L; }
|
|
|
| 3 Давлатбек, 22 ноября 2024 г. 9:21:33 |
| Oldimgakusan so'rasang bo'lmaydimi?
|
|
|
| 4 Миролим, 22 ноября 2024 г. 9:21:09 |
| tinchmi
|
|
|
| 5 Давлатбек, 22 ноября 2024 г. 9:20:45 |
| Zo'r
|
|
|
| 6 Миролим, 22 ноября 2024 г. 9:20:37 |
| salam
|
|
|
| 7 Дмитриев Дмитрий Андреевич, 22 февраля 2022 г. 10:12:22 |
| Легко решается за O(m)... Один простой dfs и все... Просто надо понять условие на дороги, а дальше очень легко) Сложнее было бы, если бы проселочные дороги были произвольными.
|
|
|
| 8 Дмитриев Дмитрий Андреевич, 06 декабря 2021 г. 12:44:50 |
| Мне кажется, или за O(nm) вообще легко, для каждого удаленного каменного ребра найти количество проселочных мостов, не?
|
|
|
| 9 Гнедов Андрей Александрович, 10 ноября 2021 г. 13:49:33 |
| На Питоне не хватает памяти, если хранить список кортежей с описанием всех дорог. Если использовать ввод из файла, то список проселочных дорог можно вообще не хранить. Файл с входными данными можно читать два раза. При первом чтении выбираем только каменные дороги и строим дерево. При втором чтении файла обрабатываем информацию о проселочных дорогах.
|
|
|
| 10 Матус Даниил Дмитриевич, 14 марта 2021 г. 21:06:15 |
| ответ 2
|
|
|
| 11 Матус Даниил Дмитриевич, 14 марта 2021 г. 21:06:09 |
| 4 5 1 2 1 2 3 1 2 4 1 1 3 0 1 4 0
|
|
|
| 12 Матус Даниил Дмитриевич, 14 марта 2021 г. 21:05:42 |
| я правда тупой и валился на 4 тесте но вот что помогло
|
|
|
| 13 Матус Даниил Дмитриевич, 14 марта 2021 г. 21:05:15 |
| итоговая асимптотика O(n+m)
|
|
|
| 14 Матус Даниил Дмитриевич, 14 марта 2021 г. 21:04:43 |
| 2)а дальше это просто дп на отрезках если грубо
|
|
|
| 15 Матус Даниил Дмитриевич, 14 марта 2021 г. 21:04:22 |
| 1)из условия понятно , что если мы соединяем вершины дерева проселочными дорогами, то вершины которые мы соединяем представляют собой пару предок-потомок либо потомок-предок
|
|
|
| 16 Матус Даниил Дмитриевич, 14 марта 2021 г. 21:02:55 |
| короче изи задача если не тупить
|
|
|
| 17 Мисник Андрей Сергеевич, 24 декабря 2019 г. 22:39:44 |
| Сейчас, когда я пытаюсь её решить, понял откуда 5 секунд. Если для каждой дороги нулевого типа проходить в родителя, то будет <=n*m операций, и это немного не залезает в тл
|
|
|
| 18 Мисник Андрей Сергеевич, 23 декабря 2019 г. 23:22:16 |
| Или (m/2)^2 это 2.5 миллиардов (все варианты выбора в худшем случае), если научиться очень быстро проверять на корректность, то можно что-нибудь придумать
|
|
|
| 19 Мисник Андрей Сергеевич, 23 декабря 2019 г. 23:19:47 |
| Можно предположить, что тут есть какое-то решение через Форд-Беллмана, оно делает 2 миллиарда операций, а это как раз на уровне 5 секунд при умелом запихивании. Но наличие очень быстрого решения за n+m при таком ограничении действительно странно.
|
|
|
| 20 Молчан Егор Дмитриевич, 23 августа 2019 г. 18:19:09 |
| СОгласен с Виталием Демиденко. Моё решение за O(n + m) работает за 0.218 сек, и это при ограничениях в 5 сек (!). Подразумевается лишний логарифм? Или чем ещё можно замедлить два DFS в 20 раз...
|
|
|
