XOR MST
Xem dạng PDF
Gửi bài giải
Điểm:
0,01 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch
Cho một đồ thị gồm ~n~ đỉnh, đỉnh thứ ~i~ có giá trị là ~a_i~. Đồ thị gồm ~\frac{N \cdot (N-1)}{2}~ cạnh, cạnh nối hai đỉnh ~i~ và ~j~ có trọng số là XOR của hai số ~a_i~ và ~a_j~. Bạn hãy tìm cây khung nhỏ nhất của đồ thị đã cho.
Input
Dòng đầu tiên gồm một số nguyên ~n~ (~1 \le n \le 10^5~) là số đỉnh của đồ thị.
Dòng thứ hai gồm ~n~ số nguyên ~a_1, a_2, \dots, a_n~ (~1 \le a_i < 2^{30}~).
Output
In một số nguyên duy nhất là cây khung nhỏ nhất của đồ thị.
Scoring
Subtask ~1~ (~20\%~):
~n \le 10^5~
~a_i < 2^{10}~
Subtask ~2~ (~20\%~):
~n \le 2500~
~a_i < 2^{20}~
Subtask ~3~ (~60\%~): Không có ràng buộc gì thêm.
Sample Input 1
5
1 2 3 4 5
Sample Output 1
8
Bình luận
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bài khó sao cho mỗi 0.01 điểm vậy
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.