Aoi và Bitaro là các điệp viên thuộc Cục Thông tin Quốc gia của nước JOI. Nhiệm vụ lần này của họ là bí mật điều tra nước IOI. Bitaro xâm nhập vào nước IOI, còn Aoi ở nước JOI để đưa ra chỉ dẫn.

Trước khi xâm nhập, Aoi và Bitaro đã có được bản đồ nước IOI. Nước IOI có \(N\) thành phố, được đánh số từ \(0\) đến \(N-1\), và \(M\) con đường, được đánh số từ \(0\) đến \(M-1\). Đường \(i\) (\(0 \le i \le M-1\)) nối hai chiều giữa thành phố \(A_i\) và thành phố \(B_i\), có độ dài \(C_i\). Có thể đi từ bất kỳ thành phố nào đến bất kỳ thành phố nào khác qua một số con đường. Bitaro di chuyển giữa các thành phố bằng những con đường này.

Ngoài ra, có \(Q\) kế hoạch điều tra. Kế hoạch thứ \(j\) (\(0 \le j \le Q-1\)) yêu cầu điều tra thành phố \(T_j\).

Cả Aoi và Bitaro đều được cung cấp toàn bộ thông tin trên trước khi Bitaro xâm nhập vào nước IOI.

Sau khi thoát khỏi nhiều kẻ truy đuổi và đánh bại các sát thủ, Bitaro cuối cùng đã vào được thành phố \(0\). Tuy nhiên, do nhiệm vụ xâm nhập quá khó khăn, cậu đã làm mất một phần thông tin về nước IOI. Cụ thể, cậu mất thông tin về độ dài của \(K\) con đường \(X_0,X_1,\ldots,X_{K-1}\), tức là không còn biết các giá trị \(C_{X_0},C_{X_1},\ldots,C_{X_{K-1}}\). Chỉ Bitaro mất những thông tin này; Aoi vẫn giữ chúng.

Bitaro lập tức báo cho Aoi biết mình đã mất thông tin độ dài của những con đường nào.

Để hoàn thành nhiệm vụ, Bitaro muốn biết một đường đi ngắn nhất từ thành phố \(0\) đến từng thành phố trong \(Q\) kế hoạch điều tra.

Aoi sẽ gửi cho Bitaro một xâu chỉ gồm các ký tự '0' và '1' để giúp cậu. Do có nguy cơ bị chặn bắt thông tin, Aoi muốn lượng thông tin gửi đi càng ít càng tốt.

Hãy viết chương trình thực hiện chiến lược của Aoi để gửi xâu khi biết thông tin về nước IOI, các kế hoạch điều tra và những con đường mà Bitaro mất thông tin. Đồng thời, hãy viết chương trình thực hiện chiến lược của Bitaro để tìm các đường đi ngắn nhất từ những thông tin cậu còn giữ và xâu nhận được từ Aoi.

Nộp bài trên LQDOJ

Trên LQDOJ, bạn nộp một tệp mã nguồn C++, nạp spy3.h, cài đặt cả hai hàm aoi và bitaro với đúng giao diện bên dưới, và không viết hàm main. Đặt các hàm phụ của hai vai trò trong các namespace riêng để tránh trùng tên khi gộp mã nguồn. Bộ chấm chạy hai vai trò trong hai tiến trình riêng biệt; không được dùng biến toàn cục để truyền thông tin giữa chúng.

Phần mô tả hai tệp và lệnh biên dịch bộ chấm mẫu dưới đây là giao diện gốc của cuộc thi, được giữ nguyên để dùng với tệp hỗ trợ chính thức đính kèm. Yêu cầu nộp một tệp ở trên chỉ thay đổi cách đóng gói mã nguồn trên LQDOJ, không thay đổi giao diện hàm, quy tắc giao tiếp hay cách tính điểm.

Chi tiết cài đặt

Bạn phải nộp hai tệp.

Tệp thứ nhất có tên Aoi.cpp, thực hiện chiến lược của Aoi. Tệp này phải nạp Aoi.h bằng chỉ thị #include và cài đặt hàm sau:

std::string aoi(int N, int M, int Q, int K, std::vector<int> A,
                std::vector<int> B, std::vector<long long> C,
                std::vector<int> T, std::vector<int> X)

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

• N là số thành phố của nước IOI.
• M là số con đường.
• Q là số kế hoạch điều tra.
• K là số con đường mà Bitaro mất thông tin về độ dài.
• A, B, C là các mảng độ dài M. Đường i (\(0 \le i \le M-1\)) nối hai chiều giữa thành phố A[i] và thành phố B[i], có độ dài C[i].
• T là mảng độ dài Q. Kế hoạch thứ j (\(0 \le j \le Q-1\)) yêu cầu điều tra thành phố T[j].
• X là mảng độ dài K, cho biết Bitaro mất thông tin độ dài của các đường X[0], X[1], ..., X[K-1].
• Giá trị trả về là xâu s mà Aoi gửi cho Bitaro.
• Mỗi ký tự của s phải là '0' hoặc '1'. Nếu không, chương trình bị chấm Wrong Answer [1].
• Độ dài của s phải không quá \(12\,000\). Nếu không, chương trình bị chấm Wrong Answer [2].

Tệp thứ hai có tên Bitaro.cpp, thực hiện chiến lược của Bitaro. Tệp này phải nạp Bitaro.h bằng chỉ thị #include và cài đặt hàm sau:

void bitaro(int N, int M, int Q, int K, std::vector<int> A,
            std::vector<int> B, std::vector<long long> C,
            std::vector<int> T, std::vector<int> X, std::string s)

Hàm này được gọi đúng một lần sau khi hàm aoi được gọi.

• N là số thành phố của nước IOI.
• M là số con đường.
• Q là số kế hoạch điều tra.
• K là số con đường mà Bitaro mất thông tin về độ dài.
• A, B, C là các mảng độ dài M. Đường i (\(0 \le i \le M-1\)) nối hai chiều giữa thành phố A[i] và thành phố B[i], có độ dài C[i]. Tuy nhiên, các phần tử C[X[0]], C[X[1]], ..., C[X[K-1]] được gán -1 thay cho độ dài thật, vì Bitaro đã mất những thông tin này.
• T là mảng độ dài Q. Kế hoạch thứ j (\(0 \le j \le Q-1\)) yêu cầu điều tra thành phố T[j].
• X là mảng độ dài K, cho biết Bitaro mất thông tin độ dài của các đường X[0], X[1], ..., X[K-1].
• s là xâu chỉ gồm các ký tự '0' và '1' mà Aoi gửi cho Bitaro.

Trong Bitaro.cpp, chương trình có thể gọi hàm sau:

void answer(const std::vector<int> &e)

Ở lần gọi thứ \(j+1\) (\(0 \le j \le Q-1\)), bạn phải đưa ra một đường đi ngắn nhất từ thành phố \(0\) đến thành phố \(T_j\), là mục tiêu của kế hoạch điều tra thứ \(j\).

• e là mảng biểu diễn đường đi ngắn nhất đó. Nếu độ dài mảng là \(n\), các phần tử e[0], e[1], ..., e[n-1] là số thứ tự của các con đường trên đường đi, theo đúng thứ tự di chuyển.
• Nếu có nhiều đường đi ngắn nhất, bạn có thể trả lời bất kỳ đường nào trong số đó.
• Mỗi phần tử của e phải nằm trong đoạn từ \(0\) đến \(M-1\). Nếu không, chương trình bị chấm Wrong Answer [3].
• Dãy đường trong e phải tạo thành một đường đi từ thành phố \(0\) đến thành phố \(T_j\). Chính xác hơn, phải tồn tại dãy \(u_0,u_1,\ldots,u_n\) sao cho \(u_0=0\), \(u_n=T_j\), và đường e[k] nối \(u_k\) với \(u_{k+1}\) với mọi \(0 \le k \le n-1\). Nếu không, chương trình bị chấm Wrong Answer [4].
• Dãy đường trong e phải là một đường đi ngắn nhất trong tất cả các đường đi từ thành phố \(0\) đến thành phố \(T_j\). Độ dài đường đi là tổng độ dài các con đường được sử dụng. Nếu đường đi không ngắn nhất, chương trình bị chấm Wrong Answer [5].
• Phải gọi answer đúng \(Q\) lần. Nếu số lần gọi không bằng \(Q\) khi hàm bitaro kết thúc, chương trình bị chấm Wrong Answer [6].

Lưu ý quan trọng

• Bạn có thể cài đặt các hàm nội bộ khác hoặc dùng biến toàn cục. Hai tệp nộp được liên kết cùng chương trình chấm thành một tệp thực thi. Mọi biến toàn cục và hàm nội bộ trong mỗi tệp phải được khai báo trong một namespace không tên để tránh xung đột với các tệp khác. Khi chấm, tệp thực thi chạy thành hai tiến trình riêng, một cho Aoi và một cho Bitaro. 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 hoặc đầu ra chuẩn, cũng không được trao đổi với các tệp khác bằng bất kỳ cách nào. Tuy nhiên, bạn được phép ghi thông tin gỡ lỗi ra đầu ra lỗi chuẩn.

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

Tệp hỗ trợ chính thức đính kèm chứa chương trình chấm mẫu và các tệp mã nguồn mẫu cần nộp.

Chương trình chấm mẫu là grader.cpp. Để thử chương trình, đặt grader.cpp, Aoi.cpp, Bitaro.cpp, Aoi.h và Bitaro.h trong cùng thư mục, rồi biên dịch bằng lệnh sau; cũng có thể dùng compile.sh trong tệp hỗ trợ:

g++ -std=gnu++20 -O2 -o grader grader.cpp Aoi.cpp Bitaro.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 thật khác chương trình chấm mẫu. Chương trình chấm mẫu chỉ chạy trong một tiến trình, đọc từ đầu vào chuẩn và ghi kết quả ra đầu ra chuẩn cùng đầu ra lỗi chuẩn.

Dữ liệu vào

Chương trình chấm mẫu đọc dữ liệu theo định dạng:

N M
A_0 B_0 C_0
A_1 B_1 C_1
...
A_{M-1} B_{M-1} C_{M-1}
Q
T_0 T_1 ... T_{Q-1}
K
X_0 X_1 ... X_{K-1}

Dữ liệu ra

Chương trình chấm mẫu ghi thông tin sau ra đầu ra chuẩn và đầu ra lỗi chuẩn (không bao gồm dấu ngoặc kép):

• Nếu chương trình bị chấm Wrong Answer [1], [2], [3], [4] hoặc [6], chương trình chấm mẫu ghi loại lỗi, chẳng hạn Wrong Answer [1], ra đầu ra lỗi chuẩn. Không có gì được ghi ra đầu ra chuẩn.
• Nếu không, độ dài xâu s do aoi trả về được ghi ra đầu ra lỗi chuẩn theo định dạng như Accepted: 2024. Đồng thời, trên dòng thứ \(j+1\) của đầu ra chuẩn (\(0 \le j \le Q-1\)), chương trình chấm mẫu ghi độ dài đường đi trong lần gọi answer thứ \(j+1\). Chương trình chấm mẫu không kiểm tra đường đi có ngắn nhất hay không.

Nếu chương trình vi phạm nhiều điều kiện gây Wrong Answer, chương trình chấm mẫu chỉ báo một loại lỗi trong số đó.

Ràng buộc

• \(2 \le N \le 10\,000\).
• \(1 \le M \le 20\,000\).
• \(1 \le Q \le 16\).
• \(1 \le K \le 300\).
• \(0 \le A_i < B_i \le N-1\) (\(0 \le i \le M-1\)).
• \((A_i,B_i) \ne (A_j,B_j)\) (\(0 \le i < j \le M-1\)).
• \(1 \le C_i \le 10^{12}\) (\(0 \le i \le M-1\)).
• \(1 \le T_j \le N-1\) (\(0 \le j \le Q-1\)).
• \(T_j \ne T_k\) (\(0 \le j < k \le Q-1\)).
• \(0 \le X_k \le M-1\) (\(0 \le k \le K-1\)).
• \(X_k \ne X_l\) (\(0 \le k < l \le K-1\)).
• Có thể đi từ bất kỳ thành phố nào đến bất kỳ thành phố nào khác qua một số con đường.
• Tất cả các giá trị đầu vào đều là số nguyên.

Cách tính điểm

Nếu có bất kỳ bộ dữ liệu nào bị chấm Wrong Answer [1] đến [6], quá giới hạn thời gian, quá giới hạn bộ nhớ hoặc lỗi chạy khác, điểm của bài là \(0\).

Nếu chương trình trả lời đúng mọi bộ dữ liệu, gọi \(L\) là độ dài lớn nhất của xâu s do hàm aoi trả về trên tất cả các bộ dữ liệu của bài. Điểm được tính như sau:

• Nếu \(1561 \le L \le 12\,000\), điểm là \(\left\lfloor\dfrac{100\,000}{L-560}\right\rfloor\).
• Nếu \(0 \le L \le 1560\), điểm là \(100\).

Ở đây, \(\lfloor x\rfloor\) là số nguyên lớn nhất không vượt quá \(x\).

Ví dụ giao tiếp

Dưới đây là dữ liệu vào mẫu cho chương trình chấm mẫu và các lời gọi hàm tương ứng.

Ví dụ giao tiếp 1

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

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

Giải thích

Lời gọi đầu tiên:

aoi(3, 3, 2, 2, [1, 0, 0], [2, 2, 1], [1, 2, 3], [2, 1], [0, 1])

Giá trị trả về là "101001". Sau đó, hàm sau được gọi:

bitaro(3, 3, 2, 2, [1, 0, 0], [2, 2, 1], [-1, -1, 3], [2, 1], [0, 1], "101001")

Trong hàm bitaro, các lời gọi trả lời lần lượt là:

answer([1])
answer([1, 0])

Có hai đường đi ngắn nhất từ thành phố \(0\) đến thành phố \(1\): đi qua đường \(1\) rồi đường \(0\), hoặc chỉ đi qua đường \(2\). Vì vậy, lời gọi answer thứ hai cũng có thể là answer([2]).

Tệp sample-01-in.txt được cung cấp trên trang cuộc thi tương ứng với dữ liệu vào mẫu \(1\). Hai tệp sample-01-in.txt và sample-02-in.txt trong dữ liệu tải về của cuộc thi đều có thể dùng làm đầu vào cho chương trình chấm mẫu.

Nguồn

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