Олимпиадный тренинг

Задача . G. Xor-MST


Задача

Темы: битмаски Конструктив Структуры данных *2300

Дан полный неориентированный граф из n вершин. Каждой вершине присвоено некоторое число ai. Вес ребра, соединяющего вершины i и j, равен ai xor aj.

Найдите вес минимального остовного дерева в этом графе.

Входные данные

В первой строке задано число n (1 ≤ n ≤ 200000) — количество вершин в графе.

Во второй строке заданы n чисел a1, a2, ..., an (0 ≤ ai < 230) — числа, присвоенные вершинам графа.

Выходные данные

Выведите одно число — вес минимального остовного дерева в заданном графе.


Примеры
№Входные данныеВыходные данные
1 5
1 2 3 4 5 
8
2 4
1 2 3 4 
8

time 2000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w645
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!
     

Загруженные файлы
Нет