Aitana và Bruno đang tham quan một vườn quốc gia ở Bolivia. Vườn quốc gia có \(N\) địa điểm và \(N-1\) con đường, mỗi đường nối hai địa điểm. Có thể đi từ bất kỳ địa điểm nào đến bất kỳ địa điểm nào khác bằng cách đi qua một số con đường.

Trong lúc đi dạo, hai người bị lạc nhau. Họ phải gặp lại bằng cách đến cùng một địa điểm vào cùng một thời điểm. Tuy nhiên, ở sâu trong rừng Amazon, họ không thể liên lạc. Mỗi người chỉ có thể dựa vào bản đồ riêng thể hiện cấu trúc các con đường. Mỗi người đã ghi các nhãn \(0,1,\ldots,N-1\) lên các địa điểm trong bản đồ của mình, nhưng cách gán nhãn của Aitana và Bruno có thể khác nhau.

Từ bây giờ, ở mỗi lượt, hai người đồng thời thực hiện một trong hai hành động: đi đến một địa điểm nối trực tiếp với địa điểm hiện tại bằng một con đường, hoặc đứng yên tại địa điểm hiện tại.

Hãy cài đặt chiến lược giúp họ gặp lại. Bài làm được trọn điểm nếu họ gặp lại trong không quá \(6d\) lượt, với \(d\) là số con đường ít nhất cần đi từ vị trí ban đầu của Aitana đến vị trí ban đầu của Bruno. Nếu họ đi ngang qua nhau ở giữa một con đường thì không được tính là gặp lại. Trong một lần chạy chương trình, bạn phải giải quyết \(Q\) tình huống.

Mô tả chi tiết

Mỗi địa điểm có một mã định danh từ \(0\) đến \(N-1\). Con đường thứ \(j\) (\(0\le j\le N-2\)) nối hai địa điểm có mã \(u_j,v_j\). Địa điểm có mã \(i\) (\(0\le i\le N-1\)) mang nhãn \(p_i\) trên bản đồ Aitana và nhãn \(q_i\) trên bản đồ Bruno. Hai dãy \((p_0,p_1,\ldots,p_{N-1})\) và \((q_0,q_1,\ldots,q_{N-1})\) đều là hoán vị của \((0,1,\ldots,N-1)\).

Aitana biết các đường nối những cặp nhãn \(A_j,B_j\) (\(0\le j\le N-2\)) và biết nhãn \(S\) của vị trí hiện tại trên bản đồ của mình. Mỗi đường thực tế nối \(u_j,v_j\) tương ứng với một đường nối \(p_{u_j},p_{v_j}\); tuy nhiên, thứ tự các đường và thứ tự hai đầu của mỗi đường khi cung cấp cho Aitana có thể bị thay đổi. Nếu vị trí ban đầu của Aitana có mã \(s\) thì \(S=p_s\).

Tương tự, Bruno biết các đường nối những cặp nhãn \(C_j,D_j\) (\(0\le j\le N-2\)), theo bản đồ của mình, và nhãn \(T\) của vị trí hiện tại. Thứ tự các đường và thứ tự hai đầu đường cũng có thể bị thay đổi. Nếu vị trí ban đầu của Bruno có mã \(t\) thì \(T=q_t\).

Từ thông tin riêng của mình, mỗi người độc lập quyết định cách di chuyển trong \(10N\) lượt tiếp theo. Aitana chọn dãy nhãn \(x_0,x_1,\ldots,x_{10N}\); Bruno chọn dãy nhãn \(y_0,y_1,\ldots,y_{10N}\). Các dãy phải thỏa mãn:

• \(x_0=S\); với mỗi \(1\le k\le 10N\), hai nhãn \(x_{k-1},x_k\) trên bản đồ Aitana chỉ cùng một địa điểm hoặc hai địa điểm nối trực tiếp bằng một con đường.
• \(y_0=T\); với mỗi \(1\le k\le 10N\), hai nhãn \(y_{k-1},y_k\) trên bản đồ Bruno chỉ cùng một địa điểm hoặc hai địa điểm nối trực tiếp bằng một con đường.

Gọi \(k^*\) là số nguyên \(k\) nhỏ nhất sao cho nhãn \(x_k\) trên bản đồ Aitana và nhãn \(y_k\) trên bản đồ Bruno chỉ cùng một địa điểm thực tế. Đây là lượt hai người gặp lại. Bài làm được trọn điểm nếu \(k^*\le 6d\).

Chi tiết cài đặt

Nộp một tệp telepathy.cpp, sử dụng chỉ thị #include "telepathy.h" và cài đặt:

std::vector<int> Aitana(int N, std::vector<int> A, std::vector<int> B,
                        int S, int subtask);
std::vector<int> Bruno(int N, std::vector<int> C, std::vector<int> D,
                       int T, int subtask);

Hàm Aitana cài đặt chiến lược của Aitana, được gọi đúng một lần cho mỗi tình huống, tổng cộng \(Q\) lần:

• N là số địa điểm.
• A, B có độ dài \(N-1\); A[j], B[j] là nhãn hai đầu của một con đường trên bản đồ Aitana (\(0\le j\le N-2\)).
• S là nhãn vị trí ban đầu của Aitana.
• subtask là số nhóm của bộ kiểm thử, thuộc \(\{1,2,3\}\).
• Hàm trả về mảng \([x_0,x_1,\ldots,x_{10N}]\), mô tả cách di chuyển theo nhãn của Aitana.

Hàm Bruno cài đặt chiến lược của Bruno, được gọi đúng một lần cho mỗi tình huống, ngay sau lời gọi Aitana, tổng cộng \(Q\) lần:

• N là số địa điểm.
• C, D có độ dài \(N-1\); C[j], D[j] là nhãn hai đầu của một con đường trên bản đồ Bruno (\(0\le j\le N-2\)).
• T là nhãn vị trí ban đầu của Bruno.
• subtask là số nhóm của bộ kiểm thử, thuộc \(\{1,2,3\}\).
• Hàm trả về mảng \([y_0,y_1,\ldots,y_{10N}]\), mô tả cách di chuyển theo nhãn của Bruno.

Các trường hợp bị chấm sai:

Chương trình có thể định nghĩa các hàm phụ trợ và biến toàn cục. Khi chấm thật, chương trình chạy thành hai tiến trình riêng, một cho Aitana và một cho Bruno; hai tiến trình không thể chia sẻ biến toàn cục.

Chương trình không được sử dụng đầu vào chuẩn, đầu ra chuẩn hoặc giao tiếp với các tệp khác 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.

Gói tệp hỗ trợ trong phần đính kèm chứa trình chấm mẫu và mã nguồn mẫu. Đặt grader.cpp, telepathy.cpp, telepathy.h trong cùng thư mục rồi biên dịch bằng:

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

Hoặc chạy ./compile.sh trong gói hỗ trợ. Khi biên dịch thành công, tệp thực thi grader được tạo ra. 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 kết quả ra đầu ra chuẩn.

Dữ liệu vào

Đầu vào của trình chấm mẫu có dạng sau; các tình huống được đánh số từ \(0\) đến \(Q-1\) và subtask là số nhóm của bộ kiểm thử:

subtask
Q
(Dữ liệu tình huống 0)
(Dữ liệu tình huống 1)
...
(Dữ liệu tình huống Q-1)

Mỗi tình huống có định dạng:

N
u_0 v_0
u_1 v_1
...
u_{N-2} v_{N-2}
p_0 p_1 ... p_{N-1}
q_0 q_1 ... q_{N-1}
s t

Ý nghĩa các biến được nêu trong phần mô tả chi tiết. Đầu vào không cung cấp trực tiếp các cạnh theo bản đồ Aitana và Bruno. Trình chấm mẫu dùng số giả ngẫu nhiên để xáo trộn các đường khi truyền đối số cho Aitana và Bruno; kết quả xáo trộn không đổi giữa các lần chạy với cùng hạt giống. Để thay hạt giống, truyền một số nguyên làm đối số đầu tiên, chẳng hạn:

./grader 20250615

Dữ liệu ra

Trình chấm mẫu xuất tổng cộng \(Q\) dòng, một dòng cho mỗi tình huống:

• Nếu hợp lệ, xuất lượt gặp nhau \(k^*\) và khoảng cách ban đầu \(d\), theo đúng thứ tự này, chẳng hạn Case #0: Accepted 5 2.
• Nếu không hợp lệ, xuất loại lỗi, chẳng hạn Case #0: Wrong Answer [1].

Trong trình chấm thật, đầu vào có thể chưa được quyết định trước khi chạy chương trình. Thông tin của các tình huống sau có thể được xác định dựa trên giá trị mà Aitana và Bruno trả về ở các tình huống trước.

Ràng buộc

Cần giải quyết nhiều nhất \(201\) tình huống, tức \(1\le Q\le 201\). Mỗi tình huống thỏa mãn:

• \(2\le N\le 200\).
• \((p_0,p_1,\ldots,p_{N-1})\) là hoán vị của các số nguyên từ \(0\) đến \(N-1\).
• \((q_0,q_1,\ldots,q_{N-1})\) là hoán vị của các số nguyên từ \(0\) đến \(N-1\).
• \(0\le u_j\le N-1\) và \(0\le v_j\le N-1\) với \(0\le j\le N-2\).
• Có thể đi từ bất kỳ địa điểm nào đến bất kỳ địa điểm nào khác qua các con đường.
• \(0\le s\le N-1\), \(0\le t\le N-1\), \(s\ne t\).

Phân nhóm

Mọi nhóm đều tuân theo các ràng buộc chung ở trên.

1. \(40\) điểm: \((p_0,p_1,\ldots,p_{N-1})=(q_0,q_1,\ldots,q_{N-1})=(0,1,\ldots,N-1)\).
2. \(40\) điểm: \(u_j=j\), \(v_j=j+1\) với mọi \(0\le j\le N-2\).
3. \(20\) điểm: Không có ràng buộc bổ sung.

Nhóm \(3\) cũng chấm các bộ kiểm thử mà tham số subtask truyền cho Aitana và Bruno bằng \(1\) hoặc \(2\).

Cách tính điểm

Với mỗi tình huống, gọi \(k^*\) là lượt gặp lại và \(d\) là khoảng cách giữa hai vị trí ban đầu. Gọi \(\alpha\) là giá trị lớn nhất của \(\frac{k^*}{d}\) trên tất cả tình huống thuộc nhóm đang xét.

Nếu chương trình bị chấm sai ở bất kỳ tình huống nào trong nhóm, điểm của nhóm đó bằng \(0\). Nếu không, bạn nhận tỉ lệ phần trăm điểm của nhóm theo bảng sau. Nếu nhiều điều kiện cùng đúng, áp dụng tỉ lệ cao nhất.

Ví dụ giao tiếp

Ví dụ 1

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

2
1
3
0 1
1 2
2 1 0
2 0 1
1 0

Lời gọi và giá trị trả về

Aitana(3, [0, 1], [1, 2], 1, 2)
[1, 0, 0, 1, 2, ..., 2]
Bruno(3, [1, 0], [2, 0], 2, 2)
[2, 2, 0, 0, 1, ..., 1]

Giải thích

Một số phần tử trong các giá trị trả về ở trên được lược bỏ, nhưng mỗi mảng đều có độ dài \(31\).

Trong hình, bên trái là bản đồ Aitana, ở giữa là cấu trúc đường của vườn quốc gia theo mã định danh, bên phải là bản đồ Bruno. Ba địa điểm có mã \(0,1,2\) tạo thành một đường đi. Trên bản đồ Aitana, chúng lần lượt mang nhãn \(2,1,0\); trên bản đồ Bruno, chúng lần lượt mang nhãn \(2,0,1\). Ban đầu Aitana ở địa điểm có mã \(1\), Bruno ở địa điểm có mã \(0\).

Vị trí của Aitana lần lượt có nhãn \(1,0,0,1,2,\ldots,2\) theo bản đồ của cô; vị trí của Bruno lần lượt có nhãn \(2,2,0,0,1,\ldots,1\) theo bản đồ của anh. Hai người gặp nhau khi kết thúc lượt thứ \(3\). Khi đó, Aitana ở nhãn \(1\) trên bản đồ của cô và Bruno ở nhãn \(0\) trên bản đồ của anh; hai nhãn này chỉ cùng một địa điểm thực tế.

Nguồn

JOI Open Contest 2025, bài Telepathy, tác giả Yui Hosaka và Hirotaka Yoneda.

Bản dịch tiếng Việt và hình từ đề của JCIOI (Ủy ban Olympic Tin học Quốc tế Nhật Bản), theo giấy phép CC BY-SA 4.0.