Submission #12,350

2024-12-12 20:45:43

cpp17

Accepted 100/100

531ms

1752 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;
}

	Sum	Test	Verdict	Time	Memory
subtask1	0/0
		1	Accepted	1ms	320 KiB
		2	Accepted	1ms	320 KiB
subtask2	7/7
		3	Accepted	2ms	320 KiB
		4	Accepted	2ms	320 KiB
		5	Accepted	2ms	320 KiB
		6	Accepted	2ms	320 KiB
		7	Accepted	2ms	320 KiB
		8	Accepted	2ms	320 KiB
		9	Accepted	2ms	320 KiB
		10	Accepted	2ms	320 KiB
		11	Accepted	1ms	320 KiB
		12	Accepted	2ms	320 KiB
		13	Accepted	2ms	320 KiB
subtask3	23/23
		14	Accepted	179ms	1080 KiB
		15	Accepted	182ms	980 KiB
		16	Accepted	182ms	1080 KiB
		17	Accepted	217ms	1128 KiB
		18	Accepted	234ms	1212 KiB
		19	Accepted	241ms	1208 KiB
		20	Accepted	159ms	1080 KiB
		21	Accepted	160ms	1212 KiB
		22	Accepted	160ms	1080 KiB
		23	Accepted	160ms	1080 KiB
		24	Accepted	209ms	1080 KiB
		25	Accepted	209ms	1112 KiB
subtask4	21/21
		26	Accepted	303ms	1592 KiB
		27	Accepted	293ms	1592 KiB
		28	Accepted	300ms	1444 KiB
		29	Accepted	310ms	1592 KiB
		30	Accepted	312ms	1596 KiB
		31	Accepted	307ms	1596 KiB
		32	Accepted	291ms	1592 KiB
		33	Accepted	296ms	1472 KiB
		34	Accepted	294ms	1592 KiB
		35	Accepted	293ms	1592 KiB
subtask5	49/49
		36	Accepted	1ms	512 KiB
		37	Accepted	1ms	320 KiB
		38	Accepted	2ms	320 KiB
		39	Accepted	2ms	320 KiB
		40	Accepted	2ms	320 KiB
		41	Accepted	2ms	320 KiB
		42	Accepted	2ms	320 KiB
		43	Accepted	2ms	320 KiB
		44	Accepted	2ms	320 KiB
		45	Accepted	2ms	320 KiB
		46	Accepted	1ms	320 KiB
		47	Accepted	2ms	320 KiB
		48	Accepted	2ms	320 KiB
		49	Accepted	179ms	1080 KiB
		50	Accepted	182ms	980 KiB
		51	Accepted	182ms	1080 KiB
		52	Accepted	217ms	1128 KiB
		53	Accepted	234ms	1212 KiB
		54	Accepted	241ms	1208 KiB
		55	Accepted	159ms	1080 KiB
		56	Accepted	160ms	1212 KiB
		57	Accepted	160ms	1080 KiB
		58	Accepted	160ms	1080 KiB
		59	Accepted	209ms	1080 KiB
		60	Accepted	209ms	1112 KiB
		61	Accepted	303ms	1592 KiB
		62	Accepted	293ms	1592 KiB
		63	Accepted	300ms	1444 KiB
		64	Accepted	310ms	1592 KiB
		65	Accepted	312ms	1596 KiB
		66	Accepted	307ms	1596 KiB
		67	Accepted	291ms	1592 KiB
		68	Accepted	296ms	1472 KiB
		69	Accepted	294ms	1592 KiB
		70	Accepted	293ms	1592 KiB
		71	Accepted	345ms	1592 KiB
		72	Accepted	368ms	1500 KiB
		73	Accepted	349ms	1612 KiB
		74	Accepted	531ms	1592 KiB
		75	Accepted	486ms	1592 KiB
		76	Accepted	514ms	1464 KiB
		77	Accepted	509ms	1464 KiB
		78	Accepted	308ms	1592 KiB
		79	Accepted	310ms	1592 KiB
		80	Accepted	307ms	1600 KiB
		81	Accepted	321ms	1752 KiB
		82	Accepted	449ms	1592 KiB
		83	Accepted	469ms	1592 KiB
		84	Accepted	462ms	1488 KiB