Bạn là một siêu trộm đang hoạt động trong thiên hà JOI.

Thiên hà có \(N\) ngôi sao, được đánh số từ \(0\) đến \(N-1\), và \(M\) thiết bị dịch chuyển, được đánh số từ \(0\) đến \(M-1\). Thiết bị \(i\) (\(0 \le i \le M-1\)) nối hai chiều giữa ngôi sao \(U_i\) và ngôi sao \(V_i\). Có thể đi từ bất kỳ ngôi sao nào đến bất kỳ ngôi sao nào khác bằng cách sử dụng các thiết bị dịch chuyển.

Một chiếc chìa khóa được giấu ở một ngôi sao, còn một chiếc rương báu được giấu ở một ngôi sao khác. Nhiệm vụ của bạn là xác định số hiệu ngôi sao \(A\) chứa chìa khóa và ngôi sao \(B\) chứa rương báu. Để thực hiện nhiệm vụ, bạn được đặt không quá \(300\) câu hỏi, mỗi câu hỏi gồm:

• Với mỗi thiết bị \(i\), chọn biến nó thành thiết bị một chiều từ \(U_i\) đến \(V_i\) hoặc từ \(V_i\) đến \(U_i\).
• Với các hướng vừa chọn, hỏi liệu có thể đi từ ngôi sao chứa chìa khóa đến ngôi sao chứa rương báu bằng các thiết bị dịch chuyển hay không.

Bạn muốn xác định \(A\) và \(B\) bằng các câu hỏi đó. Để được đánh giá cao, bạn cần dùng càng ít câu hỏi càng tốt. Cho thông tin về thiên hà, hãy cài đặt chiến lược xác định hai ngôi sao này.

Giao diện hàm

Bạn phải nộp tệp thief.cpp, nạp thief.h bằng chỉ thị #include và cài đặt hàm sau:

void solve(int N, int M, std::vector<int> U, std::vector<int> V)

Hàm này được gọi đúng một lần cho mỗi bộ dữ liệu:

• N là số ngôi sao.
• M là số thiết bị dịch chuyển.
• U và V là hai mảng có độ dài \(M\). Với mỗi \(0 \le i \le M-1\), U[i] và V[i] lần lượt là \(U_i\) và \(V_i\), hai đầu của thiết bị \(i\).

Trong thief.cpp, bạn được gọi các hàm sau:

int query(std::vector<int> x)

Hàm này đặt một câu hỏi. Tham số x phải là mảng có độ dài \(M\). Với mỗi \(0 \le i \le M-1\):

• Nếu x[i] bằng \(0\), thiết bị \(i\) chỉ cho phép đi từ \(U_i\) đến \(V_i\).
• Nếu x[i] bằng \(1\), thiết bị \(i\) chỉ cho phép đi từ \(V_i\) đến \(U_i\).

Hàm trả về \(1\) nếu có thể đi từ ngôi sao \(A\) đến ngôi sao \(B\) bằng các thiết bị đã được định hướng như trên; nếu không, hàm trả về \(0\).

• Nếu độ dài của x không bằng \(M\), chương trình bị chấm Wrong Answer [1].
• Nếu một phần tử của x khác \(0\) và \(1\), chương trình bị chấm Wrong Answer [2].
• Không được gọi query quá \(300\) lần. Nếu vượt giới hạn này, chương trình bị chấm Wrong Answer [3].

void answer(int A, int B)

Hàm này báo đáp án: ngôi sao A chứa chìa khóa và ngôi sao B chứa rương báu.

• A phải là số nguyên trong đoạn từ \(0\) đến \(N-1\). Nếu không, chương trình bị chấm Wrong Answer [4].
• B phải là số nguyên trong đoạn từ \(0\) đến \(N-1\). Nếu không, chương trình bị chấm Wrong Answer [5].
• Nếu báo sai số hiệu ngôi sao, chương trình bị chấm Wrong Answer [6].
• Phải gọi answer đúng một lần. Nếu gọi từ hai lần trở lên, chương trình bị chấm Wrong Answer [7]. Nếu solve kết thúc mà chưa gọi answer, chương trình bị chấm Wrong Answer [8].

Bạn được cài đặt các hàm phụ và khai báo biến toàn cục để sử dụng nội bộ. Chương trình nộp bài không được đọc hay ghi đầu vào chuẩn, đầu ra chuẩn, hoặc trao đổi với các tệp khác bằng bất kỳ cách nào. Tuy nhiên, được phép ghi thông tin gỡ lỗi ra đầu ra lỗi chuẩn.

Bộ chấm mẫu

Gói bộ chấm mẫu chứa grader.cpp và mã nguồn mẫu của tệp cần nộp. Đặt grader.cpp, thief.cpp, thief.h trong cùng một thư mục. Lệnh biên dịch bộ chấm mẫu là:

g++ -std=gnu++20 -O2 -o grader grader.cpp thief.cpp

Cũng có thể chạy ./compile.sh trong gói. Khi biên dịch thành công, tệp thực thi grader được tạo ra.

Bộ chấm thật khác với bộ chấm mẫu. Bộ chấm mẫu chạy trong một tiến trình, đọc dữ liệu từ đầu vào chuẩn và ghi kết quả ra đầu ra chuẩn. Những thao tác nhập xuất này do bộ chấm mẫu thực hiện, không phải chương trình bạn nộp.

Dữ liệu vào của bộ chấm mẫu có dạng:

N M A B
U_0 V_0
U_1 V_1
...
U_{M-1} V_{M-1}

Các giá trị \(A,B\) chỉ được cung cấp cho bộ chấm mẫu; hàm solve chỉ nhận \(N,M,U,V\).

Bộ chấm mẫu xuất thông tin sau, không kèm dấu ngoặc kép:

• Nếu trả lời đúng, bộ chấm in số lần gọi query, chẳng hạn Accepted: 25.
• Nếu trả lời sai, bộ chấm in loại lỗi, chẳng hạn Wrong Answer [4].

Nếu chương trình đồng thời vi phạm nhiều điều kiện, bộ chấm mẫu chỉ báo một loại lỗi. Bộ chấm mẫu có thể kết thúc chương trình ngay khi phát hiện lỗi.

Cách phản hồi của bộ chấm

Ở một số bộ dữ liệu, bộ chấm thật có tính thích nghi (adaptive). Nghĩa là bộ chấm không cố định đáp án ngay từ đầu, mà đưa ra phản hồi dựa trên các lần gọi query trước đó. Tuy nhiên, luôn bảo đảm tồn tại ít nhất một đáp án không mâu thuẫn với tất cả các phản hồi của bộ chấm.

Dữ liệu vào

Bài nộp nhận dữ liệu qua các đối số của những hàm được mô tả ở trên, không đọc đầu vào chuẩn.

Dữ liệu ra

Bài nộp không ghi đầu ra chuẩn. Kết quả được trả qua giá trị trả về của các hàm được mô tả ở trên.

Ràng buộc

• \(2 \le N \le 10000\).
• \(1 \le M \le 15000\).
• \(0 \le A \le N-1\) và \(0 \le B \le N-1\).
• \(A \ne B\).
• \(0 \le U_i < V_i \le N-1\) với mọi \(0 \le i \le M-1\).
• \((U_i,V_i) \ne (U_j,V_j)\) với mọi \(0 \le i < j \le M-1\).
• Có thể đi từ bất kỳ ngôi sao nào đến bất kỳ ngôi sao nào khác bằng các thiết bị dịch chuyển hai chiều ban đầu.

Chấm điểm

1. \(7\) điểm: \(M=N-1\), \(U_i=i\), \(V_i=i+1\) với mọi \(0 \le i \le M-1\).
2. \(13\) điểm: \(M=N-1\), \(U_i=0\), \(V_i=i+1\) với mọi \(0 \le i \le M-1\).
3. \(2\) điểm: \(M=N-1\), \(N \le 8\).
4. \(8\) điểm: \(M=N-1\), \(N \le 50\).
5. \(5\) điểm: \(M=N-1\), \(N \le 150\).
6. \(5\) điểm: \(M=N-1\), \(N \le 250\).
7. \(40\) điểm: \(M=N-1\).
8. \(20\) điểm: Không có ràng buộc bổ sung.

Với nhóm \(7\), nếu có bất kỳ bộ dữ liệu nào trong nhóm bị trả lời sai, vượt giới hạn thời gian, vượt giới hạn bộ nhớ hoặc gặp lỗi thực thi, điểm của nhóm bằng \(0\). Nếu không, gọi \(T\) là số lần gọi query lớn nhất trên tất cả các bộ dữ liệu của riêng nhóm \(7\). Điểm của nhóm được xác định như sau:

Với nhóm \(8\), nếu có bất kỳ bộ dữ liệu nào trong nhóm bị trả lời sai, vượt giới hạn thời gian, vượt giới hạn bộ nhớ hoặc gặp lỗi thực thi, điểm của nhóm bằng \(0\). Nếu không, gọi \(T\) là số lần gọi query lớn nhất trên tất cả các bộ dữ liệu của riêng nhóm \(8\). Điểm của nhóm được xác định như sau:

Điểm của các nhóm \(1,2,3,4,5,6\) không phụ thuộc vào số lần gọi query, miễn là không vượt quá \(300\) lần. Tuy nhiên, nếu gọi nhiều hơn \(70\) lần, hệ thống của kỳ thi gốc có thể hiển thị thông báo Output is partially correct dù điều này không làm giảm điểm của các nhóm đó.

Ví dụ giao tiếp

Ví dụ dưới đây gồm dữ liệu vào của bộ chấm mẫu và chuỗi lời gọi hàm tương ứng. Phần Output biểu diễn lời gọi và giá trị trả về, không phải dữ liệu mà chương trình nộp bài ghi ra đầu ra chuẩn.

Ví dụ 1

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

5 4 0 4
0 1
0 3
1 2
1 4

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

solve(5, 4, [0, 0, 1, 1], [1, 3, 2, 4])
  query([0, 1, 0, 0]) -> 1
  query([1, 1, 1, 0]) -> 0
  query([0, 0, 1, 0]) -> 1
  query([0, 0, 1, 1]) -> 0
  answer(0, 4)

Giải thích

Lần gọi query thứ nhất định hướng các thiết bị như sau:

Có thể đi từ ngôi sao \(0\) đến ngôi sao \(4\) bằng cách lần lượt dùng thiết bị \(0\) và \(3\), nên giá trị trả về là \(1\).

Lần gọi query thứ hai định hướng các thiết bị như sau:

Không thể đi từ ngôi sao \(0\) đến ngôi sao \(4\), nên giá trị trả về là \(0\).

Lần gọi query thứ ba định hướng các thiết bị như sau:

Có thể đi từ ngôi sao \(0\) đến ngôi sao \(4\), nên giá trị trả về là \(1\).

Với các hướng ở lần gọi query thứ tư, không thể đi từ ngôi sao \(0\) đến ngôi sao \(4\), nên giá trị trả về là \(0\).

Lời gọi answer(0, 4) báo rằng chìa khóa ở ngôi sao \(0\) và rương báu ở ngôi sao \(4\).

Ví dụ này thỏa mãn ràng buộc của các nhóm \(3,4,5,6,7,8\). Tệp sample-01-in.txt được nhắc đến trong đề gốc tương ứng với dữ liệu vào này. Mã nguồn mẫu đi kèm bộ chấm mẫu thực hiện đúng chuỗi lời gọi ở trên.

Giới hạn

Giới hạn thời gian là \(2\) giây; giới hạn bộ nhớ là \(1024\) MB.

Nguồn

Bản dịch tiếng Việt từ đề tiếng Anh và tiếng Nhật của Ủy ban Olympic Tin học Nhật Bản, JOI 2024/2025, vòng tuyển chọn mùa xuân, ngày thi thứ hai. Đề gốc và bản dịch được cung cấp theo giấy phép CC BY-SA 4.0.