The 23rd Japanese Olympiad in Informatics (JOI 2023/2024)
Spring Training/Qualifying Trial
March 20–24, 2024 (Komaba, Tokyo)
Contest 1 – Spy 3

Spy 3
Aoi and Bitaro are spies belonging to the National Information Bureau of JOI country. Their mission thistime is to conduct undercover investigation into the IOI country. Bitaro inﬁltrates into the IOI country, while
Aoi gives instructions to Bitaro from the JOI country.
Before the inﬁltration, Aoi and Bitaro obtained a map of the IOI country. The IOI country has N cities,
numbered from 0 to N − 1. Moreover, there are M roads in the IOI country, numbered from 0 to M − 1. Road i(0 ≤ i ≤ M − 1) connects city Ai and city Bi bidirectionally, with a length of Ci . It is possible to travel between
any pair of cities by passing some roads. Bitaro moves between cities in the IOI country by passing these roads.
Additionally, there are Q investigation plans. The j-th plan (0 ≤ j ≤ Q − 1) involves investigating city T j inthe IOI country.
All the information above were ﬁrst given to both Aoi and Bitaro. Then, Bitaro proceeded with the inﬁltration
into the IOI country.
Bitaro successfully evaded numerous pursuers, defeated assassins, and ﬁnally managed to inﬁltrate into city
0 of the IOI country. However, due to the extremely diﬃcult nature of the inﬁltration operation, Bitaro lost
some of the information about the IOI country. Speciﬁcally, Bitaro lost information about the length of K roads,
namely the roads X0 , X1 , . . . , XK−1 . In other words, Bitaro no longer knows the values of C X0 , C X1 , . . . , C XK−1 .
Note that while Bitaro lost this information, Aoi still retains it.
Bitaro immediately reported to Aoi which road lengths’ information he had lost.
To accomplish the mission, Bitaro wants to know a shortest path from city 0 to each of the cities targeted by
the Q investigation plans.
Aoi will send Bitaro a string where each character is either ’0’ or ’1’ to assist him. Due to the risk ofinterception, Aoi wants to minimize the content sent to Bitaro.
Write a program to implement Aoi’s strategy for sending a string to Bitaro, given the information about theIOI country, the investigation plans, and the roads Bitaro lost information about. Also, write a program toimplement Bitaro’s strategy for ﬁnding the shortest paths given the information he possesses and the string sent
by Aoi.

Spy 3– 1 / 7

The 23rd Japanese Olympiad in Informatics (JOI 2023/2024)
Spring Training/Qualifying Trial
March 20–24, 2024 (Komaba, Tokyo)
Contest 1 – Spy 3

Implementation Details
You should submit 2 ﬁles.
The ﬁrst ﬁle is Aoi.cpp. This ﬁle is intended to implement Aoi’s strategy and should implement the following
functions. The program should include Aoi.h using the preprocessor directive #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)
This function is called only once for each test case.
◦ The parameter N is the number of cities in IOI Kingdom N.
◦ The parameter M is the number of roads in IOI Kingdom M.
◦ The parameter Q is the number of investigation plans Q.
◦ The parameter K is the number of roads that Bitaro lost the length information of, denoted by K.
◦ The parameters A, B, C are arrays of length M. They mean the road i (0 ≤ i ≤ M − 1) connects thecity A[i] and the city B[i] bidirectionally, with a length of C[i].
◦ The parameter T is an array of length Q. It means the j-th plan (0 ≤ j ≤ Q−1) involves investigatingcity T[j].
◦ The parameter X is an array of length K. It indicates that Bitaro lost the length information of roads
X[0], X[1], . . . , X[K-1].
◦ The return value is the string s that Aoi sends to Bitaro.
◦ Each character of the string s must be either ’0’ or ’1’. If this condition is not met, your program
will be judged as Wrong Answer [1].
◦ The length of string s must be at most 12 000. If this condition is not met, your program will be
judged as Wrong Answer [2].
The second ﬁle is Bitaro.cpp. This ﬁle is intended to implement Bitaro’s strategy and should implement
the following functions. The program should include Bitaro.h using the preprocessor directive #include.

Spy 3– 2 / 7

The 23rd Japanese Olympiad in Informatics (JOI 2023/2024)
Spring Training/Qualifying Trial
March 20–24, 2024 (Komaba, Tokyo)
Contest 1 – Spy 3• 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)
This function is called only once after the function aoi is called.
◦ The parameter N is the number of cities in IOI Kingdom N.
◦ The parameter M is the number of roads in IOI Kingdom M.
◦ The parameter Q is the number of investigation plans Q.
◦ The parameter K is the number of roads that Bitaro lost the length information of, denoted by K.
◦ The parameters A, B, C are arrays of length M. They mean the road i (0 ≤ i ≤ M − 1) connects thecity A[i] and the city B[i] bidirectionally, with a length of C[i].
◦ The parameter T is an array of length Q. It means the j-th plan (0 ≤ j ≤ Q−1) involves investigatingcity T[j].
◦ The parameter X is an array of length K. It indicates that Bitaro lost the length information of roads
X[0], X[1], . . . , X[K-1].
◦ The argument s is a string where each character is either ’0’ or ’1’, representing the string sent by
Aoi to Bitaro.
Within Bitaro.cpp, your program can call the following function.

⋆ void answer(const std::vector<int> &e)In the ( j + 1)-th call (0 ≤ j ≤ Q − 1) to this function, you have to answer the shortest path from city 0 tocity T j , which is the target of the j-th investigation plan.
⋄ The parameter e is an array that represents the shortest path from city 0 to city T j .
⋄ Let n be the length of the array e. The elements e[0], e[1], . . . , e[n-1] are the indices of roads inthe shortest path from city 0 to city T j , in the order of traversal.
⋄ If there are multiple possible shortest paths, any of them can be chosen as the answer.
⋄ Each element of the parameter e must be between 0 and M − 1. If this condition is not met, yourprogram will be judged as Wrong Answer [3].
⋄ The sequence of roads indicated by the argument e must form a path from city 0 to city T j . Moreformally, it must satisfy the following conditions.
There exists a sequence of numbers u0 , u1 , . . . , un such that
* u0 = 0.
* un = T j .
* The road e[k] (where 0 ≤ k ≤ n − 1) connects city uk and city uk+1 .
If these conditions are not met, your program will be judged as Wrong Answer [4].

Spy 3– 3 / 7

The 23rd Japanese Olympiad in Informatics (JOI 2023/2024)
Spring Training/Qualifying TrialMarch 20–24, 2024 (Komaba, Tokyo)
Contest 1 – Spy 3⋄ If the sequence of roads indicated by the argument e is not the shortest path from city 0 to city T jamong all paths starting from city 0 and ending at city T j , your program will be judged as WrongAnswer [5]. Here, the length of the path is deﬁned as the sum of the lengths of the roads used.
⋄ The function answer must be called exactly Q times. If the number of calls to the function answer
is not equal to Q at the end of the execution of the function bitaro, your program will be judged asWrong Answer [6].

Important Notices• Your program can implement other functions for internal use, or use global variables. Submitted ﬁles
will be compiled with the grader, and become a single executable ﬁle. All global variables and internalfunctions should be declared in an unnamed namespace to avoid conﬂiction with other ﬁles. When it isgraded, it will be executed as two processes of Aoi and Bitaro. The process of Aoi and the process ofBitaro cannot share global variables.
• Your program must not use the standard input and the standard output. Your program must not communicate with other ﬁles by any methods. However, your program may output debugging information tothe standard error.

Compilation and Test Run
You can download an archive ﬁle from the contest webpage which contains the sample grader to test yourprogram. The archive ﬁle also contains a sample source ﬁle of your program.
The sample grader is the ﬁle grader.cpp. In order to test your program, put grader.cpp, Aoi.cpp,Bitaro.cpp, Aoi.h, Bitaro.h in the same directory, and run the following command to compile your programs. Instead, you may run compile.sh contained in the archive ﬁle.
g++ -std=gnu++20 -O2 -o grader grader.cpp Aoi.cpp Bitaro.cpp
When the compilation succeeds, the executable ﬁle grader is generated.
Note that the actual grader is diﬀerent from the sample grader. The sample grader will be executed as a single
process, which will read input data from the standard input and write the results to the standard output and thestandard error output.

Spy 3– 4 / 7

The 23rd Japanese Olympiad in Informatics (JOI 2023/2024)
Spring Training/Qualifying Trial
March 20–24, 2024 (Komaba, Tokyo)
Contest 1 – Spy 3

Input for the Sample Grader
The sample grader reads the following data from the standard input.
NMA0 B0 C0A1 B1 C1..
.
A M−1 BM−1 C M−1
Q
T 0 T 1 . . . T Q−1
K
X0 X1 . . . XK−1

Output of the Sample Grader
The sample grader outputs the following information to the standard output and the standard error output(quotes for clarity).
• If your program is judged as Wrong Answer [1], [2], [3], [4], or [6], the sample grader writes its typeas ‘Wrong Answer [1]” in the standard error output. Nothing will be output to the standard output.
• If not, the length of the returned string s from the function aoi will be output to the standard error
output in the format “Accepted: 2024”. Additionally, the length of the path in the ( j + 1)-th call(0 ≤ j ≤ Q − 1) to the answer function will be output to ( j + 1)-th line of the standard output. The
sample grading program does not check whether the path is the shortest.
If your program meets the conditions of several types of Wrong Answer, the sample grader reports only oneof them.

Constraints
All input data satisﬁes the following conditions:• 2 ≤ N ≤ 10 000.
• 1 ≤ M ≤ 20 000.
• 1 ≤ Q ≤ 16.

Spy 3– 5 / 7

The 23rd Japanese Olympiad in Informatics (JOI 2023/2024)
Spring Training/Qualifying Trial
March 20–24, 2024 (Komaba, Tokyo)
Contest 1 – Spy 3• 1 ≤ K ≤ 300.
• 0 ≤ Ai < Bi ≤ N − 1 (0 ≤ i ≤ M − 1).
• (Ai , Bi ) , (A j , B j ) (0 ≤ i < j ≤ M − 1).
• 1 ≤ Ci ≤ 1012 (0 ≤ i ≤ M − 1).
• 1 ≤ T j ≤ N − 1 (0 ≤ j ≤ Q − 1).
• T j , T k (0 ≤ j < k ≤ Q − 1).
• 0 ≤ Xk ≤ M − 1 (0 ≤ k ≤ K − 1).
• Xk , Xl (0 ≤ k < l ≤ K − 1).
• You can travel from any city to any other city by traversing some roads.
• All input values are integers.

Grading
If your program is judged as any type of Wrong Answer [1] - [6] (see Implementation Details) or any typeof runtime errors (TLE (Time Limit Exceeded), MLE (Memory Limit Exceeded), Abnormal End, etc.) in anyof the test cases, your score is 0 points.
Otherwise, the grading is based on the maximum length of the returned string s from the function aoi,denoted as L, across all test cases for this task.
⌊⌋
100 000• If 1561 ≤ L ≤ 12 000, the score ispoints.
L − 560• If 0 ≤ L ≤ 1560, the score is 100 points.
Here, ⌊x⌋ represents the largest integer that is not greater than x.

Spy 3– 6 / 7

The 23rd Japanese Olympiad in Informatics (JOI 2023/2024)
Spring Training/Qualifying TrialMarch 20–24, 2024 (Komaba, Tokyo)
Contest 1 – Spy 3

Sample Communication
Here is a sample input for the sample grader and corresponding function calls.
Sample Input 1

Sample Function Calls
CallCall

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

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

0 2 2

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

Return value"101001"

2answer([1])

2 1answer([1, 0])

20 1The shortest path from city 0 to city 1, is achieved either by traversing roads 1 and 0 in this order, or simply
passing through road 2. Therefore, for the second call to the answer function in this sample, it is also acceptableto call answer([2]).
The ﬁle that can be downloaded from the contest site, sample-01-in.txt, corresponds to input example 1.
The ﬁles sample-01-in.txt and sample-02-in.txt included in the downloadable ﬁles from the contest
site can be used as input for the sample grader.

Spy 3– 7 / 7