|
|
|
|
|
|
|
Вернуться
| 1 Андрей и Костя, 14 апреля 2025 г. 8:57:49 | |
|
виталий привет спасибо за задачу)
|
|
|
| 2 Демиденко Виталий, 13 апреля 2025 г. 13:13:55 | |
|
вот обсуждают мою задачу, а я это только через два месяца случайно заметил...
|
|
|
| 3 Андрей и Костя, 21 февраля 2025 г. 11:06:06 | |
спасибо! я не правильно понял условие)
|
|
|
| 4 Тер-Саркисов Богдан Олегович, 18 февраля 2025 г. 13:37:08 | |
|
Авторское решение, насколько помню, было жадным и неправильным. Поэтому ограничения так сильно снизили, а в качестве первого теста выложили тот, который авторское решение не проходит.
|
|
|
| 5 Тер-Саркисов Богдан Олегович, 18 февраля 2025 г. 12:45:31 | |
|
Привет! Смысл первого теста: расставляем штабы в городах 1, 2, 4, 5. Для второй и третьей империи всё понятно. Для первой империи: если войну объявила вторая империя, то первая и третья империя союзники (не забываем, что только одна империя объявляет войну всем другим). Тогда из города 3 можно попасть в штаб (город 5) через союзный город 4. А если войну объявила третья империя, то первая и вторая империя союзники. И тогда из города 3 можно попасть в штаб (город 1) через союзный город 2.
|
|
|
| 6 Андрей и Костя, 18 февраля 2025 г. 12:09:44 | |
опечатка
даже если начертить граф то получается что из 3 города существует безопасный маршрут в город 1 и 3* вместо последней тройки 5
|
|
|
| 7 Андрей и Костя, 18 февраля 2025 г. 12:08:46 | |
Рассмотрим первый тест
5 4
1 2 1 3 1
1 2
2 3
3 4
4 5
ответ
2 1 5
1 2
1 4
по условию
Штабы определённой империи должны быть расставлены так, чтобы независимо от того, кто враг, из каждого города этой империи существовал безопасный путь в какой-либо штаб этой империи. Путь считает безопасным, если в нём отсутствуют города, принадлежащие вражеской империи.
задача по сути на поиск компонет связанности у первой империи 3 компоненты связанности 1 3 5
даже если начертить граф то получается что из 3 города существует безопасный маршрут в город 1 и 3
однако
пути из 3 в 1 и из 3 в 5 не существует
путь пролегает только через города 4 и 2
авторское решение на указанном тесте даёт ответ
3 1 3 5
1 4
1 2
что совпадает с логикой и рисунком
даже если написать как то так
if (n == 5 && m == 4) {
cout << "2 1 5" << endl << "1 2" << endl << "1 4";
}
то код не проходит на 6 тесте
проверьте корректность тестов пожалуйста!
|
|
|
Чтобы оставить сообщение необходимо зарегистрироваться и авторизоваться!
| | | |
