Aoi dan Bitaro adalah mata-mata dari Biro Informasi Nasional negara JOI. Misi mereka kali ini adalah menyelidiki negara IOI secara menyamar. Bitaro menyusup ke negara IOI, sedangkan Aoi memberi instruksi kepadanya dari negara JOI.

Sebelum penyusupan, Aoi dan Bitaro memperoleh peta negara IOI. Negara IOI memiliki $N$ kota bernomor $0$ hingga $N-1$ dan $M$ jalan bernomor $0$ hingga $M-1$. Jalan $i$ $(0\le i\le M-1)$ menghubungkan kota $A_i$ dan $B_i$ dalam dua arah, dengan panjang $C_i$. Setiap pasangan kota dapat dicapai melalui beberapa jalan. Bitaro berpindah antarkota di negara IOI melalui jalan-jalan tersebut.

Selain itu, ada $Q$ rencana penyelidikan. Rencana ke-$j$ $(0\le j\le Q-1)$ adalah menyelidiki kota $T_j$ di negara IOI.

Semua informasi di atas mula-mula diberikan kepada Aoi dan Bitaro. Kemudian Bitaro mulai menyusup ke negara IOI.

Bitaro berhasil menghindari banyak pengejar, mengalahkan para pembunuh, dan akhirnya menyusup ke kota $0$ di negara IOI. Namun, karena operasi penyusupan sangat sulit, ia kehilangan sebagian informasi tentang negara IOI. Tepatnya, ia kehilangan informasi panjang $K$ jalan, yaitu jalan $X_0,X_1,\ldots,X_{K-1}$. Dengan kata lain, Bitaro tidak lagi mengetahui nilai $C_{X_0},C_{X_1},\ldots,C_{X_{K-1}}$. Meskipun Bitaro kehilangan informasi ini, Aoi masih memilikinya.

Bitaro segera melaporkan kepada Aoi jalan-jalan mana yang informasi panjangnya hilang.

Untuk menyelesaikan misi, Bitaro ingin mengetahui suatu jalur terpendek dari kota $0$ ke setiap kota yang dituju oleh $Q$ rencana penyelidikan.

Aoi akan mengirimkan string yang setiap karakternya adalah 0 atau 1 kepada Bitaro untuk membantunya. Karena berisiko disadap, Aoi ingin meminimalkan isi yang dikirim kepada Bitaro.

Tulislah program yang mengimplementasikan strategi Aoi untuk mengirim string kepada Bitaro, berdasarkan informasi negara IOI, rencana penyelidikan, dan jalan-jalan yang informasinya hilang dari Bitaro. Tulislah pula program yang mengimplementasikan strategi Bitaro untuk menemukan jalur-jalur terpendek berdasarkan informasi yang dimilikinya dan string kiriman Aoi.

Detail Implementasi

Anda harus mengumpulkan dua berkas.

Berkas pertama adalah Aoi.cpp. Berkas ini mengimplementasikan strategi Aoi dan fungsi berikut. Program harus menyertakan Aoi.h menggunakan direktif praprosesor #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)

Fungsi ini dipanggil hanya sekali untuk setiap kasus uji.

• Parameter N adalah jumlah kota di IOI Kingdom, yaitu $N$.
• Parameter M adalah jumlah jalan di IOI Kingdom, yaitu $M$.
• Parameter Q adalah jumlah rencana penyelidikan, yaitu $Q$.
• Parameter K adalah jumlah jalan yang informasi panjangnya hilang dari Bitaro, yaitu $K$.
• Parameter A, B, C adalah array sepanjang $M$. Jalan $i$ $(0\le i\le M-1)$ menghubungkan kota A[i] dan B[i] dalam dua arah, dengan panjang C[i].
• Parameter T adalah array sepanjang $Q$. Rencana ke-$j$ $(0\le j\le Q-1)$ adalah menyelidiki kota T[j].
• Parameter X adalah array sepanjang $K$. Bitaro kehilangan informasi panjang jalan X[0], X[1], ..., X[K-1].
• Nilai kembalian adalah string $s$ yang dikirim Aoi kepada Bitaro.
• Setiap karakter string $s$ harus berupa 0 atau 1. Jika tidak, program dinilai Wrong Answer [1].
• Panjang string $s$ harus paling banyak $12\,000$. Jika tidak, program dinilai Wrong Answer [2].

Berkas kedua adalah Bitaro.cpp. Berkas ini mengimplementasikan strategi Bitaro dan fungsi berikut. Program harus menyertakan Bitaro.h menggunakan direktif praprosesor #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)

Fungsi ini dipanggil hanya sekali setelah fungsi aoi dipanggil.

• Parameter N adalah jumlah kota di IOI Kingdom, yaitu $N$.
• Parameter M adalah jumlah jalan di IOI Kingdom, yaitu $M$.
• Parameter Q adalah jumlah rencana penyelidikan, yaitu $Q$.
• Parameter K adalah jumlah jalan yang informasi panjangnya hilang dari Bitaro, yaitu $K$.
• Parameter A, B, C adalah array sepanjang $M$. Jalan $i$ $(0\le i\le M-1)$ menghubungkan kota A[i] dan B[i] dalam dua arah, dengan panjang C[i].
• Parameter T adalah array sepanjang $Q$. Rencana ke-$j$ $(0\le j\le Q-1)$ adalah menyelidiki kota T[j].
• Parameter X adalah array sepanjang $K$. Bitaro kehilangan informasi panjang jalan X[0], X[1], ..., X[K-1].
• Argumen s adalah string yang setiap karakternya berupa 0 atau 1, yaitu string yang dikirim Aoi kepada Bitaro.

Di dalam Bitaro.cpp, program dapat memanggil fungsi berikut.

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

Pada pemanggilan ke-$(j+1)$ $(0\le j\le Q-1)$ fungsi ini, Anda harus melaporkan jalur terpendek dari kota $0$ ke kota $T_j$, tujuan rencana penyelidikan ke-$j$.

• Parameter e adalah array yang merepresentasikan jalur terpendek dari kota $0$ ke kota $T_j$.
• Misalkan $n$ adalah panjang array e. Elemen e[0], e[1], ..., e[n-1] adalah indeks jalan pada jalur terpendek dari kota $0$ ke kota $T_j$, sesuai urutan perjalanan.
• Jika terdapat beberapa jalur terpendek, jalur mana pun boleh dipilih sebagai jawaban.
• Setiap elemen parameter e harus berada di antara $0$ dan $M-1$. Jika tidak, program dinilai Wrong Answer [3].
• Urutan jalan yang ditunjukkan argumen e harus membentuk jalur dari kota $0$ ke kota $T_j$. Secara formal, syarat-syarat berikut harus dipenuhi.

Terdapat barisan angka $u_0,u_1,\ldots,u_n$ sedemikian sehingga:

• $u_0=0$.
• $u_n=T_j$.
• Jalan e[k], dengan $0\le k\le n-1$, menghubungkan kota $u_k$ dan $u_{k+1}$.

Jika syarat-syarat ini tidak dipenuhi, program dinilai Wrong Answer [4].

• Jika urutan jalan pada argumen e bukan jalur terpendek dari kota $0$ ke kota $T_j$ di antara semua jalur yang berawal di kota $0$ dan berakhir di kota $T_j$, program dinilai Wrong Answer [5]. Panjang jalur didefinisikan sebagai jumlah panjang jalan yang digunakan.
• Fungsi answer harus dipanggil tepat $Q$ kali. Jika jumlah pemanggilannya tidak sama dengan $Q$ saat fungsi bitaro selesai dieksekusi, program dinilai Wrong Answer [6].

Catatan Penting

• Program boleh mengimplementasikan fungsi lain untuk penggunaan internal atau menggunakan variabel global. Berkas-berkas yang dikumpulkan akan dikompilasi bersama grader menjadi satu berkas executable. Semua variabel global dan fungsi internal harus dideklarasikan dalam namespace tanpa nama agar tidak berbenturan dengan berkas lain. Saat penilaian, program dijalankan sebagai dua proses, yaitu proses Aoi dan proses Bitaro. Kedua proses tidak dapat berbagi variabel global.
• Program tidak boleh menggunakan masukan standar maupun keluaran standar. Program tidak boleh berkomunikasi dengan berkas lain dengan cara apa pun. Namun, program boleh menuliskan informasi debug ke keluaran galat standar.

Kompilasi dan Pengujian

Anda dapat mengunduh arsip dari situs kompetisi yang berisi grader contoh untuk menguji program. Arsip tersebut juga berisi contoh kode sumber program.

Grader contoh adalah berkas grader.cpp. Untuk menguji program, letakkan grader.cpp, Aoi.cpp, Bitaro.cpp, Aoi.h, dan Bitaro.h dalam direktori yang sama, lalu jalankan perintah berikut untuk mengompilasi program. Sebagai alternatif, jalankan compile.sh yang tersedia dalam arsip.

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

Jika kompilasi berhasil, berkas executable grader akan dihasilkan.

Grader sebenarnya berbeda dari grader contoh. Grader contoh dijalankan sebagai satu proses yang membaca data dari masukan standar dan menuliskan hasil ke keluaran standar serta keluaran galat standar.

Masukan untuk Grader Contoh

Grader contoh membaca data berikut dari masukan standar:

$$ \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\ \cdots\ T_{Q-1}\\ K\\ X_0\ X_1\ \cdots\ X_{K-1} \end{array} $$

Keluaran Grader Contoh

Grader contoh menuliskan informasi berikut ke keluaran standar dan keluaran galat standar (tanda kutip digunakan untuk memperjelas).

• Jika program dinilai Wrong Answer [1], [2], [3], [4], atau [6], grader contoh menuliskan jenisnya, seperti Wrong Answer [1], ke keluaran galat standar. Tidak ada yang ditulis ke keluaran standar.
• Jika tidak, panjang string $s$ yang dikembalikan fungsi aoi ditulis ke keluaran galat standar dengan format Accepted: 2024. Selain itu, panjang jalur pada pemanggilan ke-$(j+1)$ $(0\le j\le Q-1)$ fungsi answer ditulis pada baris ke-$(j+1)$ keluaran standar. Grader contoh tidak memeriksa apakah jalurnya terpendek.

Jika program memenuhi syarat beberapa jenis Wrong Answer, grader contoh hanya melaporkan salah satunya.

Batasan

Semua data masukan memenuhi syarat berikut:

• $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)$.
• Setiap kota dapat dicapai dari kota mana pun dengan melewati beberapa jalan.
• Semua nilai masukan adalah bilangan bulat.

Penilaian

Jika program mendapat jenis Wrong Answer [1]–[6] apa pun (lihat Detail Implementasi) atau galat eksekusi apa pun (TLE, batas waktu terlampaui; MLE, batas memori terlampaui; penghentian abnormal, dan sebagainya) pada kasus uji mana pun, nilainya adalah $0$ poin.

Jika tidak, penilaian didasarkan pada panjang maksimum string $s$ yang dikembalikan fungsi aoi di antara semua kasus uji dalam soal ini. Panjang maksimum tersebut dilambangkan dengan $L$.

• Jika $1561\le L\le 12\,000$, nilainya adalah $\left\lfloor\frac{100\,000}{L-560}\right\rfloor$ poin.
• Jika $0\le L\le 1560$, nilainya adalah $100$ poin.

Di sini, $\lfloor x\rfloor$ menyatakan bilangan bulat terbesar yang tidak melebihi $x$.

Contoh Komunikasi

Berikut adalah masukan untuk grader contoh dan pemanggilan fungsi yang bersesuaian.

Masukan 1

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

Contoh Pemanggilan Fungsi

Jalur terpendek dari kota $0$ ke kota $1$ dapat diperoleh dengan melewati jalan $1$ lalu jalan $0$, atau cukup melewati jalan $2$. Jadi, pada pemanggilan kedua fungsi answer dalam contoh ini, pemanggilan answer([2]) juga diterima.

Berkas sample-01-in.txt yang dapat diunduh dari situs kompetisi bersesuaian dengan contoh masukan $1$.

Berkas sample-01-in.txt dan sample-02-in.txt yang terdapat dalam unduhan dari situs kompetisi dapat digunakan sebagai masukan untuk grader contoh.