|
|
| 2 Замешаев Михаил Алексеевич, 03 июля 2020 г. 11:49:13 |
| Есть похожая задача - 538 Радио
|
|
|
| 3 Винк В В, 26 августа 2018 г. 11:57:06 |
| О(N^2) = 0.015 сек.
|
|
|
| 4 Алтыбай Назарбек, 24 января 2014 г. 10:20:26 |
| Решил за N^2logN
|
|
|
| 5 Фёдоров Александр Игоревич, 28 ноября 2013 г. 14:23:50 |
Добавьте тест:
4
0 100
1 100
0 -100
1 -100
А то глупые решения в которых находятся мин расстояния для каждой вершины, а затем нахождятся из них максимум проходят все тесты
|
|
|
| 6 Хворых Павел, 24 июня 2012 г. 12:06:46 |
Эта задача сложна выводом, и только им
Как оказалось, вывод был единственной проблемой в моем решении
Вот пример правильного вывода (ответ в s):
cout.precision(2);
cout << fixed << s;
Если это можно сделать проще, просьба, написать как
(интересуют именно потоки, через printf не надо)
|
|
|
| 7 Баранов Евгений Викторович, 29 марта 2012 г. 10:44:54 |
| Обычный алгоритм Прима, но чтобы по памяти пройти делайте на массивах , а не на всяких STL-их штучках. Да и расстояния до вывода храните в квадрате.
|
|
|
| 8 Жусупов Нурлан(FizMat), 04 октября 2011 г. 20:46:05 |
| Бин поиск рулит :D
|
|
|
| 9 ..., 25 апреля 2011 г. 13:03:11 |
| Самые быстрые решения - с помощью триангуляции?
|
|
|
| 10 ..., 25 апреля 2011 г. 11:28:55 |
У Вас слабые тесты. У меня в решении получаются несоединенные компоненты связности (делал жадный выбор ребер), но тем не менее Accepted. Предлагаю добавить тест, и сделать реджадж
4
0 0
0 5
1000 1000
1000 1005
Мое решение дает ответ 5 (что разумеется не верно)
|
|
|
| 11 Прищенко Богдан Олегович, 23 ноября 2009 г. 19:33:27 |
Сделал для себя вывод, что в таких задачах лучше хранить значение кварата расстояния вместо самого расстояния, тогда меньше шансов на реальных соревнованиях недобрать баллов/получить штрафную попытку из-за точности. Корень ведь вещь в большинстве случаев иррациональная.
Разумеется. Тем более так еще и быстрее программа работает.
|
|
|
| 12 Карелин Виталий Александрович, 28 марта 2009 г. 13:55:34 |
Чёрт! Шесть раз неудачно отослал решение на сайт, и только потом заметил, что координаты вещественные! Отсюда вывод - читайте внимательней условия)))
читайте внимательней условия! :)
|
|
|
| 13 Карелин Виталий Александрович, 26 марта 2009 г. 18:26:56 |
Что-то часто встречаю утверждение, что Краскела и Прима - n^2 Наверное я чего-то не понимаю...
Все верно. Сложность n^2, просто вы неэффективно реализуете эти алгоритмы. Алгоритм Прима очень похож на алгорим Дейкстры, ну а Дейкстра всем известно, что имеет квадратичную сложность (его тоже хочется реализовывать кубически, однако так же будет неэффективно).
|
|
|
| 14 Сабанин Евгений Александрович, 11 декабря 2008 г. 16:52:11 |
А радиостанция может стоять за пределами города?
Под "в каждом городе необходимо построить радиостанцию..." понимается, что на территории города и никак не за пределами и не внутри другого города ;) по-моему тут слишком даже все ясно.
|
|
|
