ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1056. Центры сети

Idea O(N)
Послано Felix_Mate 4 авг 2015 12:55
I got AC! It's nice problem!
My algo works at O(3*N)=O(N).
1)BFS from any vertex and find the most remote vertex (let V);
2)BFS from V and find the most remote vertex (let U);
3)Create path from U and V; vertex(vertexes) in the middle is answer.

Edited by author 04.08.2015 12:56
Re: Idea O(N)
Послано Skeef79 4 ноя 2019 15:11
It can be done easier , look here https://codeforces.com/blog/entry/17974?locale=ru