Se proporciona una secuencia de números enteros de longitud n. Si la operación bitwise AND entre dos elemenots ai y aj (ai & aj) no es cero, se establcee una arista entre los índices i y j con un peso igual a la suma de los valores ai + aj. El objetivo es encontrar la distancia más corta desde el nodo 1 a todos los demás nodos en este grafo.

Entrada

La primera línea contiene un entero positivo n. La segunda línea contiene n enteros, a1 hasta an.

Salida

Se debe imprimir una sola línea con n enteros. El i-ésimo entero representa la distancia más corta del nodo 1 al nodo i. Si un nodo es inalcanzable, se debe imprimir -1.

Ejemplo de Entrada

5
1 5 6 7 8

Ejemplo de Salida

0 6 17 8 -1

Nota

Para el 100% de los datos, se cumple que 1 ≤ n ≤ 105 y 0 ≤ ai ≤ 230.

Estrategia de Solución

La clave de este problema reside en la construcción eficiente del grafo. Podemos interpretar los n índices de la secuencia como n nodos iniciales. Dado que los valores ai pueden ser hasta 230, sus representaciones binarias pueden tener hasta 31 bits. Introducimos nodos adicionales para representar cada uno de estos 31 bits (del bit 0 al bit 30). Si el j-ésimo bit de ai es 1, creamos una arista entre el nodo que representa ai y el nodo que representa el j-ésimo bit. El peso de esta arista será ai. Después de construir esta estructura de grafo expandida, podemos aplicar un algoritmo de camino más corto, como Dijkstra, para calcular las distancias desde el nodo 1 a todos los demás nodos.

Es crucial dimensionar adecuadamente la estructura de datos para las aristas, considerando el número total de nodos (n más los 31 nodos de bit).

Código de Solución

#include <iostream>
#include <vector>
#include <queue>
#include <limits>

const long long INF = std::numeric_limits<long long>::max();
const int MAXN = 100005;
const int MAX_BITS = 31;

struct Edge {
    int to;
    long long weight;
};

std::vector<Edge> adj[MAXN + MAX_BITS];
long long distances[MAXN + MAX_BITS];
bool visited[MAXN + MAX_BITS];
long long values[MAXN];

// Estructura para el nodo en la cola de prioridad de Dijkstra
struct DijkstraNode {
    int id;
    long long dist;

    bool operator>(const DijkstraNode& other) const {
        return dist > other.dist;
    }
};

// Función para agregar una arista bidireccional
void add_edge(int u, int v, long long w) {
    adj[u].push_back({v, w});
    adj[v].push_back({u, w});
}

void dijkstra(int start_node, int num_nodes) {
    for (int i = 1; i <= num_nodes; ++i) {
        distances[i] = INF;
        visited[i] = false;
    }

    distances[start_node] = 0;
    std::priority_queue<DijkstraNode, std::vector<DijkstraNode>, std::greater<DijkstraNode>> pq;
    pq.push({start_node, 0});

    while (!pq.empty()) {
        DijkstraNode current = pq.top();
        pq.pop();

        int u = current.id;
        if (visited[u]) {
            continue;
        }
        visited[u] = true;

        for (const auto& edge : adj[u]) {
            int v = edge.to;
            long long weight = edge.weight;
            if (distances[u] != INF && distances[u] + weight < distances[v]) {
                distances[v] = distances[u] + weight;
                pq.push({v, distances[v]});
            }
        }
    }
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n;
    std::cin >> n;

    int total_nodes = n + MAX_BITS;

    for (int i = 1; i <= n; ++i) {
        std::cin >> values[i];
        // Conectar nodo 'i' a los nodos de bits correspondientes
        for (int j = 0; j < MAX_BITS; ++j) {
            if ((values[i] & (1 << j)) != 0) {
                // El nodo para el bit 'j' se mapea a 'n + j + 1'
                add_edge(i, n + j + 1, values[i]);
            }
        }
    }

    // Ejecutar Dijkstra desde el nodo 1
    dijkstra(1, total_nodes);

    // Imprimir resultados
    for (int i = 1; i <= n; ++i) {
        if (distances[i] == INF) {
            std::cout << -1 << (i == n ? "" : " ");
        } else {
            std::cout << distances[i] << (i == n ? "" : " ");
        }
    }
    std::cout << std::endl;

    return 0;
}