123502024-12-12 20:45:43szilAzugandcpp17Elfogadva 100/100531ms1752 KiB
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int MAXN = 200'001;
const int K = 21;
const ll INF = 1e9;

int v[MAXN], dist[K][K];

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int n, q; cin >> n >> q;
	for (int i = 1; i <= n; i++) {
		cin >> v[i];
	}
	for (int i = 0; i < K; i++) {
		for (int j = 0; j < K; j++) {
			if (i != j) dist[i][j] = INF;
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < K; j++) {
			for (int k = 0; k < K; k++) {
				if ((v[i] & (1<<j)) && (v[i] & (1<<k))) {
					dist[j][k] = min(dist[j][k], 1);
				}
			}
		}
	}
	for (int k = 0; k < K; k++) {
		for (int i = 0; i < K; i++) {
			for (int j = 0; j < K; j++) {
				dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
			}
		}
	}
	while (q--) {
		int a, b; cin >> a >> b;
		if (a == b) {
			cout << "0\n";
			continue;
		}
		int ans = INF;
		for (int i = 0; i < K; i++) {
			for (int j = 0; j < K; j++) {
				if ((v[a] & (1<<i)) && (v[b] & (1<<j))) {
					ans = min(ans, dist[i][j]);
				}
			}
		}
		cout << (ans==INF?-1:ans+1) << "\n";
	}
	return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva1ms320 KiB
2Elfogadva1ms320 KiB
subtask27/7
3Elfogadva2ms320 KiB
4Elfogadva2ms320 KiB
5Elfogadva2ms320 KiB
6Elfogadva2ms320 KiB
7Elfogadva2ms320 KiB
8Elfogadva2ms320 KiB
9Elfogadva2ms320 KiB
10Elfogadva2ms320 KiB
11Elfogadva1ms320 KiB
12Elfogadva2ms320 KiB
13Elfogadva2ms320 KiB
subtask323/23
14Elfogadva179ms1080 KiB
15Elfogadva182ms980 KiB
16Elfogadva182ms1080 KiB
17Elfogadva217ms1128 KiB
18Elfogadva234ms1212 KiB
19Elfogadva241ms1208 KiB
20Elfogadva159ms1080 KiB
21Elfogadva160ms1212 KiB
22Elfogadva160ms1080 KiB
23Elfogadva160ms1080 KiB
24Elfogadva209ms1080 KiB
25Elfogadva209ms1112 KiB
subtask421/21
26Elfogadva303ms1592 KiB
27Elfogadva293ms1592 KiB
28Elfogadva300ms1444 KiB
29Elfogadva310ms1592 KiB
30Elfogadva312ms1596 KiB
31Elfogadva307ms1596 KiB
32Elfogadva291ms1592 KiB
33Elfogadva296ms1472 KiB
34Elfogadva294ms1592 KiB
35Elfogadva293ms1592 KiB
subtask549/49
36Elfogadva1ms512 KiB
37Elfogadva1ms320 KiB
38Elfogadva2ms320 KiB
39Elfogadva2ms320 KiB
40Elfogadva2ms320 KiB
41Elfogadva2ms320 KiB
42Elfogadva2ms320 KiB
43Elfogadva2ms320 KiB
44Elfogadva2ms320 KiB
45Elfogadva2ms320 KiB
46Elfogadva1ms320 KiB
47Elfogadva2ms320 KiB
48Elfogadva2ms320 KiB
49Elfogadva179ms1080 KiB
50Elfogadva182ms980 KiB
51Elfogadva182ms1080 KiB
52Elfogadva217ms1128 KiB
53Elfogadva234ms1212 KiB
54Elfogadva241ms1208 KiB
55Elfogadva159ms1080 KiB
56Elfogadva160ms1212 KiB
57Elfogadva160ms1080 KiB
58Elfogadva160ms1080 KiB
59Elfogadva209ms1080 KiB
60Elfogadva209ms1112 KiB
61Elfogadva303ms1592 KiB
62Elfogadva293ms1592 KiB
63Elfogadva300ms1444 KiB
64Elfogadva310ms1592 KiB
65Elfogadva312ms1596 KiB
66Elfogadva307ms1596 KiB
67Elfogadva291ms1592 KiB
68Elfogadva296ms1472 KiB
69Elfogadva294ms1592 KiB
70Elfogadva293ms1592 KiB
71Elfogadva345ms1592 KiB
72Elfogadva368ms1500 KiB
73Elfogadva349ms1612 KiB
74Elfogadva531ms1592 KiB
75Elfogadva486ms1592 KiB
76Elfogadva514ms1464 KiB
77Elfogadva509ms1464 KiB
78Elfogadva308ms1592 KiB
79Elfogadva310ms1592 KiB
80Elfogadva307ms1600 KiB
81Elfogadva321ms1752 KiB
82Elfogadva449ms1592 KiB
83Elfogadva469ms1592 KiB
84Elfogadva462ms1488 KiB