Розбір

Problem Author:	Maksym Shvedchenko
Prepared by:	Maksym Shvedchenko
Editorial by:	Maksym Shvedchenko

Let $d_{i} = b_{i} & (\sim a_{i})$ . Then, there is an edge between vertex $i$ and vertex $j$ if and only if $d_{i} & d_{j} \neq = 0$ .

Group 1: $a_{1} = a_{i} (1 \leq i \leq n)$ , $b_{1} = b_{i} (1 \leq i \leq n)$

In this group $d_{i}$ will be the same for all vertices, which means that if they are non-zero, the graph is complete, i.e., one can go directly from one vertex to another. Thus, if $d_{i} \neq = 0$ , the output for the query $x$ , $y$ is $c_{x} + c_{y}$ , else -1. Time complexity: $O (n + q)$

Memory complexity: $O (n)$

Group 2: $n \leq 100$ , $q \leq 100$

In this group we can build our graph, and answer each query in $O (m \cdot l o g (n))$ using Dijkstra Algorithm.

Time complexity: $O (q \cdot n^{3} \cdot l o g (n))$

Memory complexity: $O (n^{2})$

Group 4: $n \leq 10000$ , $a_{i} \leq 1 0^{6} (1 \leq i \leq n)$ , $b_{i} \leq 1 0^{6} (1 \leq i \leq n)$

Let's look how our path will proceed now. It will alternate between normal and auxiliary vertices. So, let's calculate the distance from each auxiliary vertex to any other (using Dijkstra's algorithm). In each query, we will iterate over the auxiliary vertices and try to reduce the path length by saying that path will go through them.

Time complexity: $O (q \cdot L OG + n \cdot L O G^{3})$

Memory complexity: $O (n \cdot L OG)$

Group 5: $c_{i} = 0$ ;

We will do everything the same, but instead of using Dijkstra, we will use DSU (Disjoint Set Union).

Group 6: $a_{i} \leq 1 0^{12} (1 \leq i \leq n)$ , $b_{i} \leq 1 0^{12} (1 \leq i \leq n)$

Let's note that if we knew the distances between every pair of auxiliary vertices, then in the query we could iterate over the starting and final auxiliary vertices. To do this, let's notice the following: previously, we used the auxiliary vertices as bridges between two normal ones, but now we will do the exact opposite. That is, we will build a new graph with $L OG$ vertices where each normal vertex will be an edge. In other words, we will add an edge between bit $i$ and bit $j$ with weight $2 \cdot r_{i}$ if both bits are set in $d_{i}$ . Then, we will run the Floyd-Warshall algorithm.

Time complexity: $O ((q + n) \cdot L O G^{2})$

Memory complexity: $O (n \cdot L OG)$

Group 6: no additional constraints

For this group, we will reverse the approach again: specifically, we will precompute the shortest path from each vertex to each bit. Then, by iterating over this bit, we will respond to the query.

Time complexity: $O (n \cdot L O G^{2} + q \cdot L OG)$

Memory complexity: $O (n \cdot L OG)$

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
 
// #pragma GCC optimize("O3")
// #pragma GCC target("avx,avx2,fma")
// #pragma GCC optimization ("unroll-loops")
// #pragma GCC target("avx,avx2,sse,sse2,sse3,sse4,popcnt")
 
using namespace std;
using namespace __gnu_pbds;
#define int long long
#define endl "\n"
#define inf 1000'000'000'000'000'000LL
#define bit(x, i) (((x) >> (i)) & 1)
 
using i64 = long long;
 
template<typename T>
using min_heap = priority_queue<T, vector<T>, greater<T>>;
template<typename T>
using graph = vector<vector<T>>;
 
template<class T, class S>
inline bool chmin(T &a, const S &b) {
    return (a > b ? a = b, 1 : 0);
}
 
template<typename T>
using vec = vector<T>;
 
using pII = pair<int, int>;
 
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n;
    cin >> n;
    vec<i64> a(n);
    for (i64 &i: a) cin >> i;
    vec<i64> b(n);
    for (i64 &i: b) cin >> i;
    vec<int> c(n);
    for (int &i: c) cin >> i;
    const int C = 40;
    vec<i64> d(n);
    for (int i = 0; i < n; i++) {
        d[i] = (~a[i]) & b[i];
    }
    vec<vec<int>> G(C, vec<int>(C, inf));
    for (int i = 0; i < C; i++) {
        G[i][i] = 0;
    }
 
    for (int i = 0; i < n; i++) {
        vec<int> bits;
        for (int j = 0; j < C; j++) {
            if (bit(d[i], j)) {
                bits.push_back(j);
            }
        }
        for (int x: bits) {
            for (int y: bits) {
                if (x == y) continue;
                chmin(G[x][y], 2 * c[i]);
            }
        }
    }
    for (int k = 0; k < C; k++) {
        for (int i = 0; i < C; i++) {
            for (int j = 0; j < C; j++) {
                chmin(G[i][j], G[i][k] + G[k][j]);
            }
        }
    }
 
    vec<vec<int>> dists(C, vector<int>(n, inf));
    for (int i = 0; i < n; i++) {
        vec<int> bits;
        vec<int> not_bits;
        for (int j = 0; j < C; j++) {
            if (bit(d[i], j)) {
                bits.push_back(j);
            } else {
                not_bits.push_back(j);
            }
        }
        for (int x: bits) {
            chmin(dists[x][i], c[i]);
        }
        for (int y: not_bits) {
            for (int x: bits) {
                chmin(dists[y][i], G[y][x] + c[i]);
            }
        }
    }
 
    int q;
    cin >> q;
    while (q--) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        int best = inf;
        for (int i = 0; i < C; i++) {
            if (!bit(d[v], i)) continue;
            chmin(best, dists[i][u] + dists[i][v]);
        }
        if (best == inf) cout << -1 << endl;
        else cout << best << endl;
    }
 
 
}