TLEoj Cup Final Day 1 - Đồ thị xor

Điểm: 1400 (thành phần)

Thời gian: 1.25s

Bộ nhớ: 256M

Input: XORG.inp

Output: XORG.out

Dạng bài

Cho một đồ thị có $2^n$ đỉnh được đánh số từ $0$ đến $2^n - 1$ và một dãy số nguyên $a_1, a_2, ..., a_m$ . Tồn tại cạnh nối giữa đỉnh $i$ và $j$ khi và chỉ khi $i\ xor\ j = a_k$ với $1 \le k \le m$ . Cho $q$ truy vấn, mỗi truy vấn gồm hai số nguyên $u, v$ , nhiệm vụ của bạn là tìm độ dài đường đi ngắn nhất từ đỉnh $u$ đến đỉnh $v$ .

Input, Output và Subtask

Input (XORG.inp)

Dòng đầu tiên gồm ba số nguyên dương $n, m, q$ $(n \le 60, m \le 20, q \le 10^6)$
Dòng thứ hai gồm $m$ số nguyên dương $a_1, a_2, ..., a_m$ .
$q$ dòng tiếp theo, mỗi dòng gồm hai số nguyên dương $u, v$ ,

Output (XORG.out)

Gồm $q$ dòng, dòng thứ $i$ là kết quả của truy vấn thứ $i$ . Nếu không tồn tại đường đi giữa hai đỉnh $u, v$ , in ra $-1$ .

Subtask

$20\%$ số điểm có $n \le 10$ .
$20\%$ số điểm khác có $n \le 20$ .
$20\%$ số điểm khác có $m = 1$ .
$20\%$ số điểm khác có $m = 2$ .
$20\%$ số điểm còn lại không có giới hạn gì thêm.

Sample 1

Input (XORG.inp)

Output (XORG.out)

Notes

Đồ thị sẽ có dạng như sau

Input (`XORG.inp`)	Output (`XORG.out`)	Note
`3 2 4`		$n = 3$ , $m = 2$ , $q = 4$
`5 3`		$a = (5, 3)$
`1 7`	`2`	Đường đi ngắn nhất là $1 \rightarrow 2 \rightarrow 7$ .
`3 5`	`2`	Đường đi ngắn nhất là $3 \rightarrow 6 \rightarrow 5$ .
`1 5`	`-1`	Không có đường đi từ $1$ đến $5$ .
`0 3`	`1`	Có đường đi trực tiếp từ $0$ đến $3$ .

Bình luận đầu tiên

Bình luận

Không có bình luận nào.