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 đưa chỉ thị cho Bitaro từ nước JOI.

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$. Ngoài ra, nước IOI có $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 giữa hai thành phố bất kỳ bằng cách đi qua một số con đường. Bitaro di chuyển giữa các thành phố ở nước IOI qua 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$) là điều tra thành phố $T_j$ ở nước IOI.

Ban đầu, cả Aoi và Bitaro đều được cung cấp toàn bộ thông tin trên. Sau đó, Bitaro bắt đầu xâm nhập vào nước IOI.

Bitaro đã tránh được nhiều kẻ truy đuổi, đánh bại các sát thủ và cuối cùng xâm nhập thành công vào thành phố $0$ của nước IOI. Tuy nhiên, do chiến dịch xâm nhập vô cùng khó khăn, Bitaro đã mất một phần thông tin về nước IOI. Cụ thể, Bitaro đã mất thông tin về độ dài của $K$ con đường, đó là các đường $X_0,X_1,\ldots,X_{K-1}$. Nói cách khác, Bitaro không còn biết các giá trị $C_{X_0},C_{X_1},\ldots,C_{X_{K-1}}$. Lưu ý rằng mặc dù Bitaro đã mất thông tin này, Aoi vẫn còn giữ nó.

Bitaro lập tức báo cho Aoi biết mình đã mất thông tin về độ 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ố là mục tiêu của $Q$ kế hoạch điều tra.

Aoi sẽ gửi cho Bitaro một xâu mà mỗi ký tự là '0' hoặc '1' để hỗ trợ cậu ấy. Do có nguy cơ bị chặn bắt thông tin, Aoi muốn giảm thiểu nội dung gửi cho Bitaro.

Hãy viết chương trình cài đặt chiến lược của Aoi để gửi một xâu cho Bitaro, khi được cho 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 cài đặt chiến lược của Bitaro để tìm các đường đi ngắn nhất từ thông tin cậu ấy có và xâu do Aoi gửi.

Chi tiết cài đặt

Bạn cần nộp 2 tệp.

Tệp thứ nhất là Aoi.cpp. Tệp này dùng để cài đặt chiến lược của Aoi và cần cài đặt các hàm sau. Chương trình phải đưa Aoi.h vào bằng chỉ thị tiền xử lý #include.

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 chỉ được gọi một lần cho mỗi bộ kiểm thử.

• Tham số N là số thành phố $N$ ở Vương quốc IOI.
• Tham số M là số con đường $M$ ở Vương quốc IOI.
• Tham số Q là số kế hoạch điều tra $Q$.
• Tham số K là số con đường mà Bitaro đã mất thông tin về độ dài, ký hiệu là $K$.
• Các tham số A, B, C là các mảng có độ dài $M$. Chúng biểu thị rằng đườ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].
• Tham số T là mảng có độ dài $Q$. Nó biểu thị rằng kế hoạch thứ $j$ ($0 \le j \le Q-1$) là điều tra thành phố T[j].
• Tham số X là mảng có độ dài $K$. Nó biểu thị rằng Bitaro đã mất thông tin về độ 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 xâu $s$ phải là '0' hoặc '1'. Nếu không thỏa mãn điều kiện này, chương trình của bạn sẽ bị chấm là Đáp án sai [1].
• Độ dài xâu $s$ không được vượt quá $12\,000$. Nếu không thỏa mãn điều kiện này, chương trình của bạn sẽ bị chấm là Đáp án sai [2].

Tệp thứ hai là Bitaro.cpp. Tệp này dùng để cài đặt chiến lược của Bitaro và cần cài đặt các hàm sau. Chương trình phải đưa Bitaro.h vào bằng chỉ thị tiền xử lý #include.

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 chỉ được gọi một lần sau khi hàm aoi được gọi.

• Tham số N là số thành phố $N$ ở Vương quốc IOI.
• Tham số M là số con đường $M$ ở Vương quốc IOI.
• Tham số Q là số kế hoạch điều tra $Q$.
• Tham số K là số con đường mà Bitaro đã mất thông tin về độ dài, ký hiệu là $K$.
• Các tham số A, B, C là các mảng có độ dài $M$. Chúng biểu thị rằng đườ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].
• Tham số T là mảng có độ dài $Q$. Nó biểu thị rằng kế hoạch thứ $j$ ($0 \le j \le Q-1$) là điều tra thành phố T[j].
• Tham số X là mảng có độ dài $K$. Nó biểu thị rằng Bitaro đã mất thông tin về độ dài của các đường X[0], X[1], ..., X[K-1].
• Đối số s là một xâu mà mỗi ký tự là '0' hoặc '1', biểu thị xâu do Aoi gửi cho Bitaro.

Trong Bitaro.cpp, chương trình của bạn có thể gọi hàm sau.

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

Trong lần gọi thứ $(j+1)$ ($0 \le j \le Q-1$) tới hàm này, bạn phải trả lời đườ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$.

• Tham số e là một mảng biểu diễn đường đi ngắn nhất từ thành phố $0$ đến thành phố $T_j$.
• Gọi $n$ là độ dài mảng e. Các phần tử e[0], e[1], ..., e[n-1] là chỉ số của các con đường trên đường đi ngắn nhất từ thành phố $0$ đến thành phố $T_j$, theo thứ tự đi qua.
• Nếu có nhiều đường đi ngắn nhất, có thể chọn bất kỳ đường nào làm đáp án.
• Mỗi phần tử của tham số e phải nằm trong khoảng từ $0$ đến $M-1$. Nếu không thỏa mãn điều kiện này, chương trình của bạn sẽ bị chấm là Đáp án sai [3].

• Dãy con đường được chỉ ra bởi đối số 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, nó phải thỏa mãn các điều kiện sau.

  Tồn tại một dãy số $u_0,u_1,\ldots,u_n$ sao cho:

  • $u_0=0$.
  • $u_n=T_j$.
  • Đường e[k] (với $0 \le k \le n-1$) nối thành phố $u_k$ với thành phố $u_{k+1}$.

  Nếu không thỏa mãn các điều kiện này, chương trình của bạn sẽ bị chấm là Đáp án sai [4].

• Nếu dãy con đường được chỉ ra bởi đối số e không phải là đường đi ngắn nhất từ thành phố $0$ đến thành phố $T_j$ trong tất cả các đường đi bắt đầu ở thành phố $0$ và kết thúc ở thành phố $T_j$, chương trình của bạn sẽ bị chấm là Đáp án sai [5]. Ở đây, độ dài đường đi được định nghĩa là tổng độ dài của các con đường được sử dụng.

• Hàm answer phải được gọi đúng $Q$ lần. Nếu số lần gọi hàm answer không bằng $Q$ khi hàm bitaro kết thúc thực thi, chương trình của bạn sẽ bị chấm là Đáp án sai [6].

Lưu ý quan trọng

• Chương trình của bạn có thể cài đặt các hàm khác để sử dụng nội bộ hoặc sử dụng biến toàn cục. Các tệp nộp sẽ được biên dịch cùng chương trình chấm thành một tệp thực thi duy nhất. Tất cả biến toàn cục và hàm nội bộ cần đượ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, chương trình được thực thi thành hai tiến trình Aoi và Bitaro. Tiến trình Aoi và tiến trình Bitaro không thể dùng chung biến toàn cục.
• Chương trình của bạn không được sử dụng đầu vào chuẩn và đầu ra chuẩn. Chương trình của bạn không được giao tiếp với các tệp khác bằng bất kỳ phương thức nào. Tuy nhiên, chương trình có thể xuất thông tin gỡ lỗi ra luồng lỗi chuẩn.

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

Bạn có thể tải từ trang web cuộc thi một tệp nén chứa chương trình chấm mẫu để kiểm thử chương trình của mình. Tệp nén cũng chứa tệp mã nguồn mẫu cho chương trình của bạn.

Chương trình chấm mẫu là tệp grader.cpp. Để kiểm thử chương trình của mình, hãy đặt grader.cpp, Aoi.cpp, Bitaro.cpp, Aoi.h, Bitaro.h vào cùng một thư mục, rồi chạy lệnh sau để biên dịch chương trình. Thay vào đó, bạn cũng có thể chạy compile.sh có trong tệp nén.

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

Khi biên dịch thành công, tệp thực thi grader được tạo ra.

Lưu ý rằng chương trình chấm thực tế khác với chương trình chấm mẫu. Chương trình chấm mẫu được thực thi dưới dạng một tiến trình duy nhất, đọc dữ liệu vào từ đầu vào chuẩn và ghi kết quả ra đầu ra chuẩn và luồng lỗi chuẩn.

Dữ liệu vào cho chương trình chấm mẫu

Chương trình chấm mẫu đọc các dữ liệu sau từ đầu vào chuẩn.

$$ \begin{array}{l} N\ M\\ A_0\ B_0\ C_0\\ A_1\ B_1\ C_1\\ \vdots\\ A_{M-1}\ B_{M-1}\ C_{M-1}\\ Q\\ T_0\ T_1\ \ldots\ T_{Q-1}\\ K\\ X_0\ X_1\ \ldots\ X_{K-1} \end{array} $$

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

Chương trình chấm mẫu xuất thông tin sau ra đầu ra chuẩn và luồng lỗi chuẩn (dấu ngoặc kép được dùng để làm rõ).

• Nếu chương trình của bạn bị chấm là Đáp án sai [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 luồng lỗi chuẩn. Không có gì được xuất ra đầu ra chuẩn.
• Nếu không, độ dài của xâu $s$ được hàm aoi trả về sẽ được xuất ra luồng lỗi chuẩn theo định dạng Accepted: 2024. Ngoài ra, độ dài đường đi trong lần gọi thứ $(j+1)$ ($0 \le j \le Q-1$) tới hàm answer sẽ được xuất ra dòng thứ $(j+1)$ của đầu ra chuẩn. Chương trình chấm mẫu không kiểm tra xem đường đi có ngắn nhất hay không.

Nếu chương trình của bạn thỏa mãn điều kiện của nhiều loại Đáp án sai, chương trình chấm mẫu chỉ báo một loại trong số đó.

Giới hạn

Mọi dữ liệu vào đều thỏa mãn các điều kiện sau:

• $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 bằng cách đi qua một số con đường.
• Tất cả giá trị đầu vào đều là số nguyên.

Nhiệm vụ con

Nếu chương trình của bạn bị chấm là bất kỳ loại Đáp án sai [1] – [6] nào (xem Chi tiết cài đặt) hoặc gặp bất kỳ loại lỗi khi chạy nào (TLE (Vượt giới hạn thời gian), MLE (Vượt giới hạn bộ nhớ), Kết thúc bất thường, v.v.) trong bất kỳ bộ kiểm thử nào, điểm của bạn là 0.

Nếu không, điểm được tính dựa trên độ 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ộ kiểm thử của bài này, ký hiệu là $L$.

• 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$ biểu thị số nguyên lớn nhất không vượt quá $x$.

Ví dụ

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.

Dữ liệu vào 1

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

Các lời gọi hàm mẫu

Ghi chú

Đường đi ngắn nhất từ thành phố $0$ đến thành phố $1$ có thể đạt được bằng cách đi qua các đường $1$ rồi $0$ theo thứ tự này, hoặc chỉ đi qua đường $2$. Vì vậy, đối với lần gọi thứ hai tới hàm answer trong ví dụ này, lời gọi answer([2]) cũng được chấp nhận.

Tệp sample-01-in.txt có thể tải từ trang web cuộc thi tương ứng với dữ liệu vào của ví dụ 1.

Các tệp sample-01-in.txt và sample-02-in.txt trong các tệp có thể tải từ trang web cuộc thi có thể được dùng làm dữ liệu vào cho chương trình chấm mẫu.