Editorial
Problem Author: | Maksym Shvedchenko |
Prepared by: | Maksym Shvedchenko |
Editorial by: | Maksym Shvedchenko |
Let . Then, there is an edge between vertex and vertex if and only if .
Group 1: ,
In this group 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 , the output for the query , is , else -1. Time complexity:
Memory complexity:
Group 2: ,
In this group we can build our graph, and answer each query in using Dijkstra Algorithm.
Time complexity:
Memory complexity:
Group 4: , ,
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:
Memory complexity:
Group 5: ;
We will do everything the same, but instead of using Dijkstra, we will use DSU (Disjoint Set Union).
Group 6: ,
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 vertices where each normal vertex will be an edge. In other words, we will add an edge between bit and bit with weight if both bits are set in . Then, we will run the Floyd-Warshall algorithm.
Time complexity:
Memory complexity:
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:
Memory complexity:
#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; } }