Đảo JOI là một công viên tự nhiên gồm \(N\) địa điểm, đánh số từ \(0\) đến \(N-1\), và một số con đường hai chiều. Mỗi đường nối hai địa điểm khác nhau, giữa một cặp địa điểm có nhiều nhất một đường, bậc của mỗi địa điểm không quá \(7\), và toàn bộ mạng đường liên thông.

Bạn cần xác định toàn bộ mạng đường bằng cách hỏi IOI-chan liệu hai địa điểm có nối được với nhau khi chỉ được phép đi qua một tập địa điểm cho trước hay không. Bạn được hỏi không quá \(45\,000\) lần.

Chi tiết cài đặt

Chương trình phải khai báo #include "park.h" và cài đặt:

void Detect(int T, int N);

Hàm được gọi đúng một lần. T là số hiệu nhóm, N là số địa điểm.

Để báo một con đường, gọi:

void Answer(int A, int B);

Số lần gọi Answer phải đúng bằng số con đường. Mỗi lần gọi phải thỏa \(0\le A<B\le N-1\) và \((A,B)\) phải là một con đường thật. Vi phạm lần lượt bị chấm Wrong Answer [1], [2]; gọi nhiều hơn một lần với cùng cặp \((A,B)\) bị [3]. Nếu Detect kết thúc mà còn đường chưa báo, nhận [6].

Có thể hỏi:

int Ask(int A, int B, int Place[]);

Mảng Place phải có đúng \(N\) phần tử. Place[i]=1 nghĩa là được phép đi qua địa điểm \(i\), còn Place[i]=0 nghĩa là không. Hàm trả về \(1\) nếu có đường đi từ \(A\) đến \(B\) chỉ qua các địa điểm được phép, ngược lại trả về \(0\).

Mỗi lời gọi phải thỏa \(0\le A<B\le N-1\), mọi Place[i] thuộc \(\{0,1\}\), và Place[A]=Place[B]=1; nếu không nhận Wrong Answer [4]. Hành vi không được đảm bảo nếu độ dài mảng khác \(N\). Gọi quá \(45\,000\) lần nhận [5].

Chương trình có thể cài đặt hàm phụ và dùng biến toàn cục. Chương trình không được đọc/ghi luồng chuẩn hoặc giao tiếp với tệp khác.

Biên dịch và chạy thử

Gói chính thức chứa trình chấm mẫu và mã nguồn mẫu. Nếu bài làm là park.c hoặc park.cpp, có thể biên dịch bằng một trong các lệnh:

gcc -std=c11 -O2 -o grader grader.c park.c -lm
g++ -std=c++14 -O2 -o grader grader.cpp park.cpp

Trình chấm thật khác trình chấm mẫu. Trình chấm mẫu chạy trong một tiến trình, đọc đầu vào chuẩn và ghi đầu ra chuẩn.

Dữ liệu vào của trình chấm mẫu

• Dòng đầu chứa \(T\).
• Dòng thứ hai chứa \(N\).
• Dòng thứ ba chứa số đường \(M\).
• \(M\) dòng tiếp theo chứa \(A_i,B_i\), mô tả một đường hai chiều.

Dữ liệu ra của trình chấm mẫu

Trình chấm mẫu in Accepted. nếu đúng; nếu sai, in một thông báo dạng Wrong Answer [1] rồi kết thúc. Nếu có nhiều lỗi, chỉ một lỗi được báo.

Ràng buộc

• \(1\le T\le 5\).
• \(2\le N\le 1\,400\).
• \(1\le M\le 1\,500\).
• Bậc mỗi địa điểm không quá \(7\).
• Đồ thị liên thông, đơn và vô hướng.

Phân nhóm

1. \(10\) điểm: \(T=1\), \(N\le 250\)
2. \(10\) điểm: \(T=2\), \(M=N-1\); địa điểm \(0,N-1\) có bậc \(1\), mọi địa điểm khác có bậc \(2\)
3. \(27\) điểm: \(T=3\), \(M=N-1\); từ \(0\) tới mỗi \(i>0\) đi qua không quá \(8\) địa điểm trung gian
4. \(30\) điểm: \(T=4\), \(M=N-1\)
5. \(23\) điểm: \(T=5\)

Giới hạn

• Thời gian: 2 giây.
• Bộ nhớ: 256 MB.
• Số lần gọi Ask: không quá \(45\,000\).

Ví dụ giao tiếp

1
6
7
0 1
0 3
1 2
1 4
2 4
2 5
3 4

Detect(1,6) được gọi. Chuỗi lời gọi minh họa là:

Lời hỏi đầu tiên chỉ cho phép đi qua các địa điểm \(2,3,4,5\), nên có đường đi từ \(3\) tới \(5\) và hàm trả về \(1\). Lời hỏi thứ hai chỉ cho phép đi qua \(0,2,4\), nên không có đường đi từ \(0\) tới \(4\) và hàm trả về \(0\). Chuỗi minh họa không nhất thiết thể hiện một thuật toán có ý nghĩa.

Nguồn

JOI 2016/2017 Spring Training Camp, ngày thi 3, bài Natural Park.