Vương quốc JOI có \(N\) hòn đảo, được đánh số từ \(1\) đến \(N\), và \(N-1\) tuyến đường biển, được đánh số từ \(1\) đến \(N-1\). Tuyến thứ \(j\) nối đảo \(A_j\) với đảo \(B_j\) theo cả hai chiều. Có thể đi từ bất kỳ đảo nào đến bất kỳ đảo nào khác bằng cách sử dụng một số tuyến đường biển.

Aoi đang lên kế hoạch du lịch ở vương quốc JOI nhưng không biết những tuyến đường biển này. Cô sẽ hỏi Bitaro, một cư dân của vương quốc, theo cách sau:

1. Aoi đưa ra hai số nguyên \(v,k\), với \(1 \le v \le N\) và \(1 \le k \le N-1\).
2. Bitaro cho biết số hiệu của đảo gần đảo \(v\) thứ \(k\) trong số \(N-1\) đảo khác \(v\). Cụ thể, gọi \(\operatorname{dist}(v,i)\) là số tuyến đường biển ít nhất cần dùng để đi từ đảo \(v\) đến đảo \(i\). Bitaro trả về số nguyên \(i\) \((1 \le i \le N, i\ne v)\) có giá trị \(\operatorname{dist}(v,i)\times N+i\) nhỏ thứ \(k\). Như vậy, các đảo được xếp theo khoảng cách tăng dần, và khi bằng khoảng cách thì theo số hiệu tăng dần.

Aoi muốn xác định tất cả các tuyến đường biển nhưng chỉ được hỏi Bitaro tối đa \(L\) lần. Cho số đảo và giới hạn số câu hỏi, hãy cài đặt chiến lược giúp Aoi tìm được tất cả các tuyến đường biển.

Chi tiết cài đặt

Nộp một tệp duy nhất tên island.cpp. Tệp này phải có chỉ thị #include "island.h" và cài đặt hàm:

void solve(int N, int L);

Hàm được gọi đúng một lần cho mỗi bộ dữ liệu. N là số đảo, còn L là số câu hỏi tối đa được phép hỏi.

Trong island.cpp, có thể gọi hai hàm sau do chương trình chấm cung cấp:

int query(int v, int k);
void answer(int x, int y);

Hàm query(v, k) đặt một câu hỏi cho Bitaro và trả về số hiệu của đảo gần đảo v thứ k, theo đúng định nghĩa trong đề.

• Phải có \(1 \le v \le N\); nếu không, nhận Wrong Answer [1].
• Phải có \(1 \le k \le N-1\); nếu không, nhận Wrong Answer [2].
• Không được gọi query quá \(L\) lần; nếu vượt quá, nhận Wrong Answer [3].

Hàm answer(x, y) báo rằng có một tuyến đường biển nối đảo x và đảo y.

• Cả x và y phải thuộc đoạn từ \(1\) đến \(N\); nếu không, nhận Wrong Answer [4].
• Phải thực sự có tuyến đường biển nối hai đảo đó: tồn tại \(j\) sao cho \((x,y)=(A_j,B_j)\) hoặc \((x,y)=(B_j,A_j)\). Nếu không, nhận Wrong Answer [5].
• Không được báo cùng một tuyến đường biển từ hai lần trở lên, kể cả khi đổi thứ tự hai đầu mút; nếu vi phạm, nhận Wrong Answer [6].
• Phải gọi answer đúng \(N-1\) lần. Nếu khi solve kết thúc mà số lần gọi không bằng \(N-1\), nhận Wrong Answer [7].

Lưu ý cài đặt

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

Chương trình chấm chính thức không thích nghi trong mọi bộ dữ liệu: các tuyến đường biển được cố định từ trước, không thay đổi theo những câu hỏi đã đặt.

Chương trình chấm mẫu

Gói tệp dành cho thí sinh chứa chương trình chấm mẫu grader.cpp, tệp mẫu island.cpp, tệp tiêu đề island.h và compile.sh. Đặt grader.cpp, island.cpp, island.h trong cùng một thư mục rồi biên dịch bằng lệnh dưới đây, hoặc chạy compile.sh:

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

Nếu biên dịch thành công, tệp thực thi grader được tạo ra. Chương trình chấm chính thức khác chương trình chấm mẫu. Chương trình 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; đây không phải quyền sử dụng đầu vào/đầu ra chuẩn của mã thí sinh.

Dữ liệu vào

N L
A_1 B_1
A_2 B_2
...
A_{N-1} B_{N-1}

Dữ liệu ra

Nếu đáp án đúng, chương trình chấm mẫu in số lần gọi query, chẳng hạn Accepted: 2024. Nếu đáp án sai, chương trình chấm mẫu in loại lỗi, chẳng hạn Wrong Answer [4]. Các dấu nháy không được in. Nếu chương trình vi phạm nhiều điều kiện, chỉ một loại lỗi được báo.

Ràng buộc

• \(3 \le N \le 300\).
• \(1 \le A_j \le N\) và \(1 \le B_j \le N\) với mọi \(1 \le j \le N-1\).
• \(A_j\ne B_j\) với mọi \(1 \le j \le N-1\).
• Có thể đi từ một đảo bất kỳ đến mọi đảo khác bằng một số tuyến đường biển.
• Tất cả giá trị đầu vào đều là số nguyên. Giá trị \(L\) được quy định theo từng nhóm dưới đây.

Phân nhóm

• Nhóm 1 (2 điểm): \(N=3\), \(L=9\).
• Nhóm 2 (4 điểm): \(L=N^2\); mỗi đảo nối trực tiếp với nhiều nhất hai đảo khác.
• Nhóm 3 (7 điểm): \(L=2N\); mỗi đảo nối trực tiếp với nhiều nhất hai đảo khác.
• Nhóm 4 (9 điểm): \(L=N^2\); đảo \(1\) nối trực tiếp với đúng ba đảo khác, mỗi đảo còn lại nối trực tiếp với nhiều nhất hai đảo khác.
• Nhóm 5 (13 điểm): \(L=3N\); đảo \(1\) nối trực tiếp với đúng ba đảo khác, mỗi đảo còn lại nối trực tiếp với nhiều nhất hai đảo khác.
• Nhóm 6 (15 điểm): \(L=N^2\).
• Nhóm 7 (22 điểm): \(L=3N\).
• Nhóm 8 (28 điểm): \(L=2N\).

Ví dụ giao tiếp

Các ví dụ sau gồm đầu vào của chương trình chấm mẫu và một chuỗi lời gọi hàm tương ứng.

Ví dụ 1

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

4 16
1 2
2 4
4 3

Lời gọi hàm

Giải thích

Chương trình thí sinh trả lời bằng các lời gọi answer, không in đáp án ra đầu ra chuẩn.

Khoảng cách từ đảo \(2\) đến các đảo \(1,3,4\) lần lượt là \(1,2,1\). Chẳng hạn, để đi từ đảo \(2\) đến đảo \(3\), có thể đi qua tuyến đường biển thứ \(2\) rồi tuyến thứ \(3\).

Xếp các đảo khác \(2\) theo \(\operatorname{dist}(2,i)\times N+i\) tăng dần thu được thứ tự \(1,4,3\). Vì thế, query(2, 1) trả về 1 và query(2, 2) trả về 4.

Ví dụ này thỏa mãn các nhóm \(2,6\), tương ứng với tệp mẫu chính thức sample-01-in.txt.

Ví dụ 2

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

5 25
5 2
3 1
1 4
1 5

Lời gọi hàm

Giải thích

Chương trình thí sinh trả lời bằng các lời gọi answer, không in đáp án ra đầu ra chuẩn.

Khoảng cách từ đảo \(1\) đến các đảo \(2,3,4,5\) lần lượt là \(2,1,1,1\). Chẳng hạn, để đi từ đảo \(1\) đến đảo \(2\), có thể đi qua tuyến đường biển thứ \(4\) rồi tuyến thứ \(1\).

Xếp các đảo khác \(1\) theo \(\operatorname{dist}(1,i)\times N+i\) tăng dần thu được thứ tự \(3,4,5,2\). Vì thế, query(1, 3) trả về 5 và query(1, 4) trả về 2.

Ví dụ này thỏa mãn các nhóm \(4,6\), tương ứng với tệp mẫu chính thức sample-02-in.txt.

Cả sample-01-in.txt và sample-02-in.txt đều có thể dùng làm đầu vào của chương trình chấm mẫu.

Nguồn

JOI 2023/2024, kỳ thi tuyển chọn mùa xuân, ngày thi thứ tư (24/03/2024). Đề của Ủy ban Olympic Tin học Nhật Bản (JCIOI). Bản dịch tiếng Việt theo giấy phép CC BY-SA 4.0.