Astro đang theo dõi các thành phố trên hành tinh Mar Sara. Ban đầu có \(N\) thành phố, được đánh số từ \(1\) đến \(N\), và chưa có con đường nào. Người Terran sẽ lần lượt xây dựng các con đường sao cho sau mỗi lần xây, hai thành phố ở hai đầu đường chưa được nối với nhau bằng một đường đi trước đó. Vì vậy, các con đường luôn tạo thành một cây sau khi xây xong.

Sau mỗi lần xây đường, bạn cần xác định hai đầu mút của con đường mới trước khi con đường tiếp theo được xây. Bạn có thể dùng SETI để hỏi về hai tập thành phố rời nhau. Với hai tập \(A\) và \(B\), SETI cho biết có hay không một con đường trực tiếp nối một thành phố thuộc \(A\) với một thành phố thuộc \(B\) trong đồ thị hiện tại.

Giao diện hàm

Trong C/C++, hãy cài đặt hàm sau trong chương trình nộp:

void run(int N);

Tệp icc.h khai báo các hàm mà grader cung cấp:

int query(int size_a, int size_b, int a[], int b[]);
void setRoad(int a, int b);

• Grader gọi run(N) một lần cho mỗi kiểm thử.
• Gọi query(size_a, size_b, a, b) để hỏi về hai tập thành phố. Hai tập phải rời nhau và các chỉ số thành phố nằm trong đoạn \([1,N]\). Hàm trả về \(1\) nếu hiện có ít nhất một con đường trực tiếp nối hai tập, ngược lại trả về \(0\).
• Khi xác định được con đường mới, gọi setRoad(a,b) với hai đầu mút. Nếu câu trả lời sai, kiểm thử hiện tại nhận \(0\) điểm và chương trình kết thúc. Nếu đây là con đường thứ \(N-1\), kiểm thử kết thúc. Nếu chưa, một con đường mới được xây trước lần gọi tiếp theo.
• Nếu run kết thúc trước khi xác định đủ \(N-1\) con đường, kiểm thử nhận \(0\) điểm.

Hãy thêm #include "icc.h" trong mã nguồn. Không cần đọc dữ liệu vào hoặc in dữ liệu ra bằng luồng chuẩn.

Phân nhóm

• Nhóm 1: \(N=15\), được gọi query nhiều nhất \(1500\) lần, chiếm \(7\%\) số điểm.
• Nhóm 2: \(N=50\), được gọi query nhiều nhất \(2500\) lần, chiếm \(11\%\) số điểm.
• Nhóm 3: \(N=100\), được gọi query nhiều nhất \(2250\) lần, chiếm \(22\%\) số điểm.
• Nhóm 4: \(N=100\), được gọi query nhiều nhất \(2000\) lần, chiếm \(21\%\) số điểm.
• Nhóm 5: \(N=100\), được gọi query nhiều nhất \(1775\) lần, chiếm \(29\%\) số điểm.
• Nhóm 6: \(N=100\), được gọi query nhiều nhất \(1625\) lần, chiếm \(10\%\) số điểm.

Để nhận điểm của một nhóm, bạn phải xác định đúng tất cả các con đường trong mọi kiểm thử của nhóm đó và không vượt quá giới hạn số lần gọi query.

Ví dụ

Ví dụ minh họa một lần chạy với \(N=4\). Mỗi dòng query cho biết kết quả grader trả về.

run(4)
query(1, 3, {1}, {2, 3, 4}) -> 0
query(1, 2, {2}, {3, 4})    -> 1
query(1, 1, {2}, {3})       -> 0
setRoad(2, 4)

query(2, 2, {2, 4}, {1, 3}) -> 0
setRoad(1, 3)

query(2, 2, {2, 4}, {1, 3}) -> 1
query(1, 2, {2}, {1, 3})    -> 0
query(1, 1, {4}, {3})       -> 0
setRoad(4, 1)

Ban đầu, con đường mới là \((2,4)\). Sau khi gọi setRoad(2,4), con đường mới tiếp theo là $(1,3). Sau đó, con đường cuối cùng là $(1,4). Truy vấn lặp lại có thể cho kết quả khác vì đồ thị đã được cập nhật.

Nguồn

CEOI 2016, ngày 1, bài 1.