fork download
copy 
  1. // Idea: compress to a 20-node "bit graph".
  2. // Put an edge between bit p and bit q if there exists some device having both bits p and q.
  3. // Then the answer for (x, y) is:
  4. //   - 1 if (A[x] & A[y]) != 0
  5. //   - else min over p in bits(A[x]), q in bits(A[y]) of dist_bit[p][q] + 1
  6. // If unreachable -> -1.  (Max answer ≤ 20)
  7.  
  8. #include <bits/stdc++.h>
  9. using namespace std;
  10.  
  11. int main() {
  12.     ios::sync_with_stdio(false);
  13.     cin.tie(nullptr);
  14.  
  15.     const int B = 20;
  16.     const int INF = 1e9;
  17.  
  18.     int N, Q;
  19.     if (!(cin >> N >> Q)) return 0;
  20.  
  21.     vector<int> A(N + 1);
  22.     for (int i = 1; i <= N; ++i) cin >> A[i];
  23.  
  24.     // dist between bits
  25.     int dist[B][B];
  26.     for (int i = 0; i < B; ++i) {
  27.         for (int j = 0; j < B; ++j) dist[i][j] = (i == j ? 0 : INF);
  28.     }
  29.  
  30.     // bits of each device
  31.     vector<array<int, B>> hasBit(N + 1);
  32.     vector<int> bitList[N + 1];
  33.  
  34.     for (int i = 1; i <= N; ++i) {
  35.         int x = A[i];
  36.         for (int b = 0; b < B; ++b) {
  37.             if (x >> b & 1) bitList[i].push_back(b);
  38.         }
  39.         // connect all bits appearing together in this device
  40.         for (int p = 0; p < (int)bitList[i].size(); ++p)
  41.             for (int q = p + 1; q < (int)bitList[i].size(); ++q) {
  42.                 int u = bitList[i][p], v = bitList[i][q];
  43.                 dist[u][v] = dist[v][u] = 1;
  44.             }
  45.     }
  46.  
  47.     // Floyd–Warshall on 20 nodes
  48.     for (int k = 0; k < B; ++k)
  49.         for (int i = 0; i < B; ++i)
  50.             for (int j = 0; j < B; ++j)
  51.                 if (dist[i][k] + dist[k][j] < dist[i][j])
  52.                     dist[i][j] = dist[i][k] + dist[k][j];
  53.  
  54.     while (Q--) {
  55.         int x, y; 
  56.         cin >> x >> y;
  57.  
  58.         // quick checks
  59.         if ((A[x] & A[y]) != 0) {
  60.             cout << 1 << '\n';
  61.             continue;
  62.         }
  63.         if (bitList[x].empty() || bitList[y].empty()) {
  64.             cout << -1 << '\n';
  65.             continue;
  66.         }
  67.  
  68.         int best = INF;
  69.         for (int p : bitList[x])
  70.             for (int q : bitList[y])
  71.                 if (dist[p][q] < INF)
  72.                     best = min(best, dist[p][q] + 1);
  73.  
  74.         cout << (best >= INF ? -1 : best) << '\n';
  75.     }
  76.  
  77.     return 0;
  78. }
  79.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
4 4
16 6 9 3
3 4
4 2
2 3
4 1
stdout
copy 
1
1
2
-1
https://ideone.com/Lbl81a
language:
C++14 (gcc 8.3)
created:
14 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!