CF Ozon 2020 G, Курони и Антихайп

Прикольная задача :D

Тут стоит порешать немного другую задачу, когда нам дан граф. Получаем, что нам нужно добавить вершину 0 и посчитать MST по ребрам (u-v, a[u] + a[v]).

Поняв это, мне захотелось написать Борувку, но я, к сожалению, не придумал как :(

А идея то достаточно простая, по сути нам надо для каждого i найти такое максимальное a[j], что a[i] AND a[j] = 0, а так же i и j лежат в разных компонентах. Можно было бы это делать корнячкой и получить n * sqrt(n) * log^2(n) :D (с SOS), а давайте просто в SOS[x] хранить два максимальных числа, которые являются подмаской x и лежат в разных компонентах. Вот и всё, задача, чтобы вспомнить эту идею.

Код: https://codeforces.com/contest/1305/submission/224607118