Second Round 2026/2027 - Swiss Olympiad in Informatics

Overview

Welcome to the Second Round of the Swiss Olympiad in Informatics! You will find below an overview of what you’ve done so far as well as a few things that you should know before getting started.

Contest ends at 2026-11-30T23:59:59+01:00

Category	Task	Total	Subtask 1	Subtask 2	Subtask 3	Subtask 4	Subtask 5	Subtask 6
Junior only	tablegroups	‒/100	‒/15	‒/16	‒/19	‒/20	‒/30
Junior only	microwaving	‒/100	‒/15	‒/17	‒/19	‒/20	‒/29
Both	standemehr	‒/100	‒/9	‒/14	‒/16	‒/23	‒/17	‒/21
Both	alpineechoes	‒/100	‒/8	‒/11	‒/22	‒/16	‒/18	‒/25
Both	fajitas	‒/100	‒/18	‒/13	‒/25	‒/12	‒/32
Both	magicforest	‒/100	‒/7	‒/8	‒/15	‒/40	‒/30
Regular only	explorer	‒/100	‒/10	‒/14	‒/15	‒/20	‒/24	‒/17
Regular only	rohrpost	‒/100	‒/6	‒/13	‒/26	‒/16	‒/18	‒/21
Both	graderpractice	‒/100	‒/25	‒/25	‒/25	‒/25

Tips

You may use any programming language to solve the tasks of the Second Round. To solve a practical task, you have to design a program, download an input file, run the program on the data in that file, write the results in another file and upload it along with the source code to the website, which will grade your submission and display the number of points that you’ve earned as well as an explanation if you did not get all the possible points. In order to read the data in the input file, make sure that your program either reads directly in that file or redirect the standard input to it (in a terminal running on Linux, Windows or macOS, you can do that by using the command ‘yourprogram < inputfile’, replacing ‘yourprogram’ and ‘inputfile’ by the paths to the actual program and input file). More elaborate explanations about how to solve the tasks of the Second Round await you on our wiki and our training page. Note that in case you get stuck on the tasks, you can move to next task and try again later: no need to solve them in order.

You should also hear about our workshops! In October and November, we offer workshops about algorithmics. It’s a great opportunity to learn all you need for the Second Round and to meet other like-minded participants. Whether you’re a beginner or an experienced programmer, it’s worth it to come. More info and registration here.

Don’t hesitate to contact us at info@soi.ch if you have any question about programming or the tasks.

Rules and Prizes

To participate, you need to either have qualified in the first round or scored 600 points in the pre-round. It may take up to five minutes after adding an additional email address in your profile or submitting something in the pre-round for your qualification status to be updated.

The Second Round has two categories: Junior and Regular. You can participate in the Junior category if you are eligible to participate in this year’s edition of SOI as well as the two next ones. If you are eligible as a junior, you can choose to participate in the Junior or in the Regular category or in both.

You qualify for the finals and the Sarnen Camp if you are placed under the

top 8 of the Junior category, and/or
top 16 of the Regular category.

Additionally, we may distribute wildcards.

We wish you good luck, hope you will enjoy solving our tasks and look forward to meeting you at our workshops.

Table Groups

Mouse Stofl loves eating fancy food. Fancy food, however, is too expensive for Stofl, so he came up with an idea: He will work at a fancy German restaurant as a waiter! That way he will have access to free fancy food from the kitchen.

Being a waiter is not an easy job. One of his tasks is collecting orders from customers. In Germany, it is customary that, for a group of mice, instead of every mouse placing an order individually, the group as a whole places one order. It is also a well-known fact that two different groups of German mice always have at least one empty chair between them, so all adjacent mice belong to the same group. In other words, a group is a maximal set of mice sitting on consecutive chairs. If no mouse is sitting at the table, there are $0$ groups.

To collect the orders, Stofl takes one piece of paper per order from the kitchen to write it down. Since Germany is renowned for its high efficiency, Stofl would like to only take exactly the amount of paper he needs so as not to appear inefficient. But since he is still new to German culture, he has difficulties determining which mouse belongs to which group, and he therefore asked you to help him find out how many pieces of paper he needs.

Subtask 1: Tiny table (15 points)

The restaurant Stofl is working at only has a very small table. Help Stofl determine the number of groups sitting at the table.

Input

The first line contains the number of test cases $T$ . For each test case you get two lines:

The first line contains a single integer $N$ — the number of chairs.
The second line contains a string of length $N$ : The current occupation $a_{0}, a_{1}, {\dots}, a_{N-1}$ . A “1” means a mouse is sitting on that chair, a “0” means an empty chair.

Output

For the $t$ -th test case, output a single line containing “Case #t: x”, where $x$ is the number of groups sitting at the table.

Limits

There are $T = 100$ test cases. In each test case we have:

$N = 3$
$a_i ∈ \{0, 1\}$

Example

Input:

Output:

Case #0: 2
Case #1: 1

To submit for this subtask, please log in.

Subtask 2: Medium table (16 points)

Stofl wasn’t happy with the food at his old restaurant, so he changed to a different restaurant with a bigger table.

Input

Same as Subtask 1.

Output

Same as Subtask 1.

Limits

There are $T = 100$ test cases. In each test case we have:

$1 \le N \le 1\,000$
$a_i ∈ \{0, 1\}$

Example

Input:

Output:

Case #0: 2
Case #1: 1

To submit for this subtask, please log in.

Subtask 3: Circular table (19 points)

The restaurant Stofl is working at wants to become even more fancy! They once heard that circular tables are super fancy, so they replaced the old table with a circular one.

Input

Same as Subtask 1. Additionally, chairs $0$ and $N-1$ are now also considered adjacent.

Output

Same as Subtask 1.

Limits

There are $T = 100$ test cases. In each test case we have:

$1 \le N \le 100\,000$
$a_i ∈ \{0, 1\}$

Example

Input:

Output:

Case #0: 1
Case #1: 1

Comment:

Case #0: Since the table is circular, there is now only 1 group.

To submit for this subtask, please log in.

Subtask 4: Busy restaurant (20 points)

The restaurant has become very popular, and some mice may be leaving or arriving at the restaurant one after another. Every time a mouse arrives or leaves, Stofl wants you to find how many groups there are now. The table is circular.

Input

The first line contains the number of test cases $T$ . For each test case:

The first line contains a single integer $N$ — the number of chairs.
The second line contains a string of length $N$ : The current occupation $a_{0}, a_{1}, {\dots}, a_{N-1}$ . A “1” means a mouse is sitting on that chair, a “0” means an empty chair. Chairs $0$ and $N-1$ are also considered adjacent.
The third line contains a single integer $Q$ — the number of events (mice leaving or arriving).
The next $Q$ lines contain a single integer $q_i$ : If there was a mouse sitting on chair $q_i$ it leaves; otherwise, a new mouse arrives and sits down there.

Output

For the $t$ -th test case, output $Q+1$ lines:

The first line should contain “Case #t: x”, where $x$ is the initial number of groups.
The next $Q$ lines should contain a single integer. The $i$ -th line should contain the number of groups after the $i$ -th event.

Limits

There are $T = 100$ test cases. In each test case we have:

$1 \le N \le 1\,000$
$0 \le Q \le 10$
$a_i ∈ \{0, 1\}$
$0 \le q_i < N$

Example

Input:

Output:

Case #0: 2
1
1
Case #1: 1
1
1
2

Comment:

Case #0: Initially, there are 2 groups. After the mouse on chair 1 leaves, there is only 1 group. When a mouse sits down at chair 0, there is still only 1 group since the table is circular and chairs 0 and 4 are adjacent.

To submit for this subtask, please log in.

Subtask 5: Super busy restaurant (30 points)

The restaurant has become so famous that a lot of mice are joining and leaving. A huge circular table has been bought accordingly.

Input

Same as Subtask 4.

Output

Same as Subtask 4.

Limits

There are $T = 100$ test cases. In each test case we have:

$1 \le N \le 1\,000\,000$
$0 \le Q \le 20\,000$
$a_i ∈ \{0, 1\}$
$0 \le q_i < N$

Example

Input:

Output:

Case #0: 2
1
1
Case #1: 1
1
1
2

To submit for this subtask, please log in.

Don’t hesitate to ask us any question about this task, programming or the website via email (info@soi.ch).

Microwaving

Mouse Stofl is a student at the Mouse-Binna-Institute (MBI) for Analog Cheese Sciences in Potsdam. Mouse Stofl is really fond of the MBI, partly because of the great hands-on courses, partly because there is an abundance of microwaves to warm up his lunch in. Unfortunately, one day, Cat Tigro decided to make the students’ lives as hard as possible by disabling all but one microwave. Now there is a long line in front of the only remaining microwave!

The $N$ mice in that line have each prepared a meal, and now they are all queuing in front of the single microwave, which can warm only one meal at a time. The meal prepared by the $i$ -th mouse is considered warm once its heat level is at least $a_i$ . Every meal starts at room temperature, which is heat level $0$ . While it is inside the microwave, its heat level rises by $x_i$ per second; once it has been taken out, it drops by $y_i$ per second. A meal never gets colder than room temperature: one that has cooled all the way back down to heat level $0$ simply stays there until it is put into the microwave again.

A meal that is taken out early therefore keeps cooling while the later meals are still being warmed. The group wants to start eating at the same time, i.e. only once the very last meal has finished warming, and at that moment every meal must still be warm.

The mice are happy to let Stofl decide for them: you may choose the order in which they use the microwave. A meal may be warmed for any real number of seconds: a warming time does not have to be a whole number of seconds. The same mouse may also use the microwave more than once: a meal may be taken out and put back in later, cooling down in between. How many seconds are needed until the whole group can start eating together?

Subtask 1: Early Lunch (15 points)

Mouse Stofl and his friends just finished the class “Cheese Optimizations” early, and have rushed to the microwave before any other classes have finished. Thus, the friend group, consisting of at most seven mice, is the only group standing in line. Having planned ahead, they stick to the plan they agreed on: they queue up in the order in which the meals are listed in the input, and each of them warms their meal exactly once, for exactly as long as they said they would. As soon as the last meal is out of the microwave the group starts eating, and only then do they find out whether the plan leaves everyone’s lunch warm enough to eat. As it is Monday, everyone has brought the same analog cheese fondue, so every meal warms up at the same rate and cools down at the same rate. Since every mouse is different, how warm they like their fondue still differs.

Input

The first line contains the number of test cases $T$ . Each test case consists of five lines:

The first line contains a single integer $N$ , the number of mice.
The second line contains $N$ integers $a_{0}, a_{1}, {\dots}, a_{N-1}$ : the heat level each meal needs to be warm.
The third line contains $N$ integers $x_{0}, x_{1}, {\dots}, x_{N-1}$ : the heat level each meal gains per second inside the microwave.
The fourth line contains $N$ integers $y_{0}, y_{1}, {\dots}, y_{N-1}$ : the heat level each meal loses per second outside the microwave.
The fifth line contains $N$ real numbers $t_{0}, t_{1}, {\dots}, t_{N-1}$ : the number of seconds for which the $i$ -th meal is warmed. Each $t_i$ has at most six decimal places.

Output

For the $t$ -th test case, output a single line “Case #t:” followed by “yes” if every meal is still warm enough for its mouse at the moment the group starts eating, i.e. if its heat level is at least $a_i$ , and “no” if at least one meal is not.

Limits

There are $T = 100$ test cases. In each test case:

$1 \le N \le 7$
$1 \le a_i \le 10^{6}$
$x_{0}= x_{1}= {\dots} = x_{N-1}$ and $1 \le x_i \le 10^{9}$
$y_{0}= y_{1}= {\dots} = y_{N-1}$ and $1 \le y_i \le 100$
$0 \le t_i \le 10^{6}$ , with at most six decimal places

Example

Input:

2
3
900 200 100
100 100 100
10 10 10
9.5 0.5 8
3
900 200 100
100 100 100
10 10 10
9.6 2.5 1.5

Output:

Case #0: no
Case #1: yes

Comment:

In the first test case the three meals are microwaved one after another in the order in which they are listed, for

9.5

0.5

and

8

seconds respectively. The heat level of the first meal increases to

9.5 \cdot 100 = 950

, and then it cools down for

0.5 + 8 = 8.5

seconds at

10

per second, which leaves it at

950 - 85 = 865

, less than the

900

it needs. The heat level of the second meal increases only to

0.5 \cdot 100 = 50

, which its

8

seconds of cooling would more than use up: it reaches room temperature after

5

seconds and simply stays at

0

. The last meal, taken out exactly when the group starts eating, is fine with heat level

8 \cdot 100 = 800

. So not every meal is warm enough, and the answer is “no”.

In the second test case the mice warm the same meals a little longer, for

9.6

2.5

and

1.5

seconds, which leaves them at heat levels

920

235

and

150

. That is enough for all three of them, since

920 \ge 900

235 \ge 200

and

150 \ge 100

, so the answer is “yes”.

To submit for this subtask, please log in.

Subtask 2: Strangers in Line (17 points)

The next day, Mouse Stofl’s class did not finish early. When he arrived at the microwave, there were already a lot of mice queuing. Unfortunately, he does not know them, and since he is shy, he does not want to ask them to reorder. Thus, Mouse Stofl is content with knowing how long it takes until everyone can start eating.

The order in which the mice use the microwave is exactly the order in which they are listed in the input, and each mouse warms their meal exactly once, in one uninterrupted turn. Compute the time this fixed queue needs.

Input

The first line contains the number of test cases $T$ . Each test case consists of four lines:

The first line contains a single integer $N$ , the number of mice.
The second line contains $N$ integers $a_{0}, a_{1}, {\dots}, a_{N-1}$ : the heat level each meal needs to be warm.
The third line contains $N$ integers $x_{0}, x_{1}, {\dots}, x_{N-1}$ : the heat level each meal gains per second inside the microwave.
The fourth line contains $N$ integers $y_{0}, y_{1}, {\dots}, y_{N-1}$ : the heat level each meal loses per second outside the microwave.

The order in which the meals are listed is the order in which they use the microwave. You may choose the warming times freely.

Output

For the $t$ -th test case, output a single line “Case #t: X”, where $X$ is the number of seconds the group needs when the meals are warmed in the listed order (each meal is warmed just long enough to still be warm at the very end). $X$ may be a real number; print it with enough digits (about 6 decimal places are always enough). An answer is accepted if its relative error is at most $10^{-6}$ (or its absolute error is at most $10^{-6}$ when the answer is below $1$ ).

Limits

There are $T = 100$ test cases. In each test case:

$1 \le N \le 2\,000$
$1 \le a_i \le 10^{6}$
$x_{0}= x_{1}= {\dots} = x_{N-1}$ and $1 \le x_i \le 10^{9}$
$y_{0}= y_{1}= {\dots} = y_{N-1}$ and $1 \le y_i \le 100$

Example

Input:

1
3
100 900 200
100 100 100
10 10 10

Output:

Case #0: 13.32

Comment:

The meals are microwaved one after another in the given order, for

2.12

9.2

and

2

seconds respectively, so the group needs

2.12 + 9.2 + 2 = 13.32

seconds.

To submit for this subtask, please log in.

Subtask 3: Warm Brie Wednesday (19 points)

Wednesday is warm brie Wednesday! Therefore, everyone brought brie for lunch. Brie has the property that regardless of how you prepare it, it will always warm up and cool down at the same rate. Since every mouse is different, how warm they like their brie differs. Meanwhile, Mouse Stofl’s friends have done some advertising for their new optimization technique, and thus all mice in the queue agreed to let Mouse Stofl reorder the queue to improve its efficiency.

Input

Same as Subtask 2, except that the order in which the meals are listed is arbitrary: you may choose the order in which the mice use the microwave, and a mouse may also take more than one turn, taking their meal out and putting it back in later.

Output

Same as Subtask 2, except that $X$ is the minimum number of seconds needed over all possibilities, instead of the time needed for the arrangement in which they are listed.

Limits

There are $T = 100$ test cases. In each test case:

$1 \le N \le 20\,000$
$1 \le a_i \le 10^{6}$
$x_{0}= x_{1}= {\dots} = x_{N-1}$ and $1 \le x_i \le 10^{9}$
$y_{0}= y_{1}= {\dots} = y_{N-1}$ and $1 \le y_i \le 100$

Example

Input:

1
3
900 200 100
100 100 100
10 10 10

Output:

Case #0: 12.41

Comment:

Microwaving the meals in the order in which they are listed here is optimal, and takes

9.31

2.1

and

1

seconds respectively, giving

9.31 + 2.1 + 1 = 12.41

seconds in total.

To submit for this subtask, please log in.

Subtask 4: Triple-Gouda Thursday (20 points)

Thursday is triple-Gouda Thursday! Everyone brought a Gouda dish. Gouda dishes have the property that they all cool down at the same rate, but depending on what the Gouda cheese is paired with, it warms up at a different rate. Since every mouse is different, how warm they like their Gouda differs.

Input

Same as Subtask 3.

Output

Same as Subtask 3.

Limits

There are $T = 100$ test cases. In each test case:

$1 \le N \le 20\,000$
$1 \le a_i \le 10^{6}$
$1 \le x_i \le 10^{9}$
$y_{0}= y_{1}= {\dots} = y_{N-1}$ and $1 \le y_i \le 100$

Example

Input:

1
3
900 200 100
100 1000 200
10 10 10

Output:

Case #0: 9.7755

Comment:

The meals are microwaved one after another in the order in which they are listed, for

9.0705

0.205

and

0.5

seconds respectively, so the total time is

9.0705 + 0.205 + 0.5 = 9.7755

seconds.

To submit for this subtask, please log in.

Subtask 5: Fusion Friday (29 points)

Friday is fusion Friday! Everyone has brought along the leftovers of the week: some of Monday’s fondue, a piece of Wednesday’s brie, what was left of Thursday’s Gouda, and whatever else was still in the fridge. With every lunch a different mixture, there is no pattern left in how a meal warms up or cools down: every meal may have its own $a_i$ , $x_i$ and $y_i$ .

Input

Same as Subtask 3.

Output

Same as Subtask 3.

Limits

There are $T = 100$ test cases. In each test case:

$1 \le N \le 20\,000$
$1 \le a_i \le 10^{6}$
$1 \le x_i \le 10^{9}$
$1 \le y_i \le 100$

Example

Input:

1
3
900 200 100
100 1000 200
2 5 10

Output:

Case #0: 9.71655

Comment:

The meals are microwaved one after another in the order in which they are listed, for

9.01405

0.2025

and

0.5

seconds respectively, so the total time is

9.01405 + 0.2025 + 0.5 = 9.71655

seconds.

To submit for this subtask, please log in.

Don’t hesitate to ask us any question about this task, programming or the website via email (info@soi.ch).

Ständemehr

Mouseland is a wonderful country organised in a hierarchy: the country consists of cantons, each canton of districts, each district of smaller districts, and so on. At the bottom of the hierarchy are the mice. There are $N$ administrative units (such as the country, a canton, or a district), and $M$ mice.

You have launched a tax-free cheese initiative and want to get it accepted. Each mouse $i$ plans to vote either Yes or No.

An administrative unit approves the initiative if a strict majority of its sub-units accept it. This is called the Ständemehr. This means, for your initiative to pass in Mouseland, a strict majority of cantons must approve it. For a canton to approve it, a strict majority of its districts must approve it, and so on down the hierarchy.

Unfortunately, your initiative is unlikely to pass, so you want to influence the vote. You can persuade any mouse to change their vote by offering it a certain amount of cheese.

What is the minimum total cost (in cheese) needed to make the initiative pass?

Subtask 1: One canton to rule them all (9 points)

In this subtask, there is one canton and up to $1\,000\,000$ voters. All voters belong directly to this canton. Each voter has a persuasion cost of 1.

Input

The first line contains the number of test cases

T

T

test cases follow, each in the following format:

The first line contains one integer

M

: the number of mice.

The second line contains

M

integers

v_i

: the initial vote of mouse

i

(

v_i = 1

for Yes and

v_i = 0

for No).

Output

For the $t$ -th test case, output a line “Case #t: X”, where $X$ is the minimum total cost needed to make the initiative pass. Test cases are numbered from $0$ to $T-1$ .

Limits

$T = 50$
$1 \le M \le 1\,000\,000$

Examples

Input:

3
6
1 0 0 1 0 0
2
0 0
8
0 0 0 1 1 1 1 1

Output:

Case #0: 2
Case #1: 2
Case #2: 0

Comment:

Case #0: Two mice must be persuaded for the initiative to pass.
Case #1: Two mice must be persuaded for the initiative to pass.
Case #2: No mice need to be persuaded for the initiative to pass.

To submit for this subtask, please log in.

Subtask 2: Counting votes (14 points)

We now have 26 cantons and up to $1\,000\,000$ voters. All voters vote directly in their respective cantons.

You want to compute the result of a provisional survey on the initiative to determine whether you need to stock up on cheese.

Input

The first line contains the number of test cases

T

T

test cases follow, each in the following format:

The first line contains one integer

M

: the number of mice.

The second line contains

M

integers

q_i

: the canton to which the mouse

i

belongs (

0 \le q_i < 26

The third line contains

M

integers

v_i

: the initial vote of mouse

i

(

v_i = 1

for Yes and

v_i = 0

for No).

Note: Each canton has at least one mouse.

Output

For the $t$ -th test case, output a line “Case #t: X”, where $X$ is $1$ if the initiative passes and $0$ otherwise. Test cases are numbered from $0$ to $T-1$ .

Limits

$T = 50$
$26 \le M \le 1\,000\,000$

Examples

Input:

1
30
0 0 0 1 1 2 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
0 1 1 1 1 0 1 0 1 0 1 0 1 0 1  0  1  0  1  0  1  0  1  0  1  0  1  0  1  0

Output:

Case #0: 0

Comment:

Canton

0

has 3 mice and 2 positive votes, so it accepts the initiative. Canton

1

has 2 mice and 2 positive votes, so it accepts the initiative. Canton

2

has 2 mice and 1 positive vote, so it rejects the initiative. All other cantons have one mouse and accept or reject the initiative according to that mouse’s vote. In total, 13 cantons accept and 13 cantons reject the initiative. The strict majority is not reached; therefore, the initiative is rejected by the country.

To submit for this subtask, please log in.

Subtask 3: More bureaucracy (16 points)

We now have three administrative levels: the country, cantons, and districts, and up to $1\,000$ mice.

Each mouse changes its mind when given a certain amount of cheese. The persuasion cost depends on the mouse.

Input

The first line contains the number of test cases

T

T

test cases follow, each in the following format:

The first line contains three integers

M

N_c

and

N_d

: the number of mice, the number of cantons, and the number of districts.

The second line contains

N_d

integers

p_i

: the canton to which the district

i

belongs. (

0 \le p_i < N_c

The third line contains

M

integers

q_i

: the district to which the mouse

i

belongs. (

0 \le q_i < N_d

The fourth line contains

M

integers

v_i

: the initial vote of mouse

i

(

v_i = 1

for Yes and

v_i = 0

for No).

The fifth line contains

M

integers

c_i

: the persuasion cost of mouse

i

Note: Each district has at least one mouse under it.

Output

For the $t$ -th test case, output a line “Case #t: X”, where $X$ is the minimum total cost needed to make the initiative pass. Test cases are numbered from $0$ to $T-1$ .

Limits

$T = 50$
$1 \le N_c \le N_d \le M \le 1\,000$
$1 \le c_i \le 10^{6}$

Examples

Input:

1
6 2 5
1 0 0 1 1
0 1 0 2 3 4
1 1 0 0 1 1
1 1 3 1 2 1

Output:

Case #0: 1

Comment:

There are 6 mice, 2 cantons, and 5 districts. Districts 0 and 2 reject the initiative by one mouse vote. Districts 1, 3, and 4 accept the initiative. Canton 0, which consists of districts 1 and 2, rejects the initiative by one district vote. Canton 1, which consists of districts 0, 3, and 4, accepts the initiative because a majority of its districts accept the initiative. To obtain a strict majority, we need to change the vote of the only mouse in district 2. This mouse has a persuasion cost of 1, so the output is 1.

To submit for this subtask, please log in.

Subtask 4: Pivotal mouse (23 points)

We now have numerous hierarchical levels. To describe these levels, you are given a list $p_{0}, p_{1}, {\dots}, p_i, {\dots}, p_{N-1}$ , where $p_i$ is the parent administrative unit of administrative unit $i$ . The top-level administrative unit is the country, which has $-1$ as its parent.

For example, the list of parents -1 0 0 2 1 1 2 2 represents the same hierarchy as in Subtask 3. We have one country ( $i=0$ ) with two cantons ( $i=1,2$ ) and five districts ( $i=3,4,5,6,7$ ). Districts $i=3,6,7$ belong to canton $i=2$ , while districts $i=4,5$ belong to canton $i=1$ .

Please note that the list of parents 7 7 1 0 0 1 1 -1 is also a valid representation of the same hierarchy, since the administrative units may be listed in any order.

A pivotal mouse is a mouse whose change of vote alone would change the outcome of the initiative. The initiative currently fails and needs one pivotal mouse to vote Yes in order to pass. You must find all possible pivotal mice; it is guaranteed that there is at least one.

Print all possible pivotal mice, that is, all mice whose vote change would make the initiative pass.

Input

The first line contains the number of test cases

T

T

test cases follow, each in the following format:

The first line contains two integers

M

N

: the number of mice, and the number of administrative units.

The second line contains

N

integers

p_i

: the unit to which the administrative unit

i

belongs. (

0 \le p_i < N

, except for one unit where

p_i = -1

The third line contains

M

integers

q_i

: the administrative unit to which the mouse

i

belongs. (

0 \le q_i < N

The fourth line contains

M

integers

v_i

: the initial vote of mouse

i

(

v_i = 1

for Yes and

v_i = 0

for No).

Notes:

The country is the root of the hierarchy, and its parent is denoted by $p_i = -1$ . There is exactly one such administrative unit.
The administrative units and mice form a tree. In other words, the hierarchy is cycle-free.
We guarantee that each administrative unit has at least one mouse somewhere below it in the hierarchy, and that all mice sit on the same level of the tree.

Output

For the $t$ -th test case, output a line “Case #t:” followed on the same line by the indexes of all possible pivotal mice in increasing order, i.e. the mice whose vote change would make the initiative pass. Test cases are numbered from $0$ to $T-1$ .

Limits

$T = 100$
$1 \le N + M \le 500\,000$

Note: the hierarchy can be very deep (up to $250\,000$ levels). If your solution uses recursion, you need to increase the stack size or the recursion limit:

C++ on Linux: run ulimit -s unlimited in the terminal before running your program (on macOS: ulimit -s 65532).
C++ on Windows: compile with the option -Wl,--stack,268435456.
Python: call sys.setrecursionlimit(10**6) after using import sys at the top of your file.

Examples

Input:

1
9 5
-1 0 0 0 0
1 1 1 2 2 3 3 4 4
1 1 1 1 0 1 0 1 1

Output:

Case #0: 4 6

Comment:

We have five administrative entities: the country and four cantons. There are nine mice.

Cantons 1 and 4 accept the initiative, while cantons 2 and 3 reject it by one vote each. Three cantons must accept the initiative for it to pass at the national level.

Therefore, we display the mice in cantons 2 and 3 that voted “No”, because changing their votes would change the acceptation of their canton, and therefore make the initiative pass at national level.

To submit for this subtask, please log in.

Subtask 5: Cheese distribution (17 points)

You now want to influence an actual vote.

Any mouse may change its mind if given 1 piece of cheese.

Input

Same as Subtask 4.

Output

For the $t$ -th test case, output a line “Case #t: X”, where $X$ is the minimum total cost needed to make the initiative pass. Test cases are numbered from $0$ to $T-1$ .

Limits

$T = 100$
$1 \le N + M \le 1\,000$

Examples

Input:

1
6 8
-1 0 0 1 2 2 1 1
3 4 3 5 6 7
1 1 0 0 1 1

Output:

Case #0: 1

Comment:

Note that this is the same structure as in the example for subtask 3. We have one country, two cantons, five districts, and six mice. As in the example for subtask 3, we obtain a majority by changing the vote of mouse 3.

To submit for this subtask, please log in.

Subtask 6: Huge cheese distribution (21 points)

There are now more mice, and they have learned to be greedy.

Each mouse changes its mind when given a certain amount of cheese. The persuasion cost depends on the mouse.

Input

Same as Subtask 4, except that each test case has an additional fifth line containing $M$ integers $c_i$ : the persuasion cost of mouse $i$ .

Output

For the $t$ -th test case, output a line “Case #t: X”, where $X$ is the minimum total cost needed to make the initiative pass. Test cases are numbered from $0$ to $T-1$ .

Limits

$T = 100$
$1 \le N + M \le 1\,000\,000$
$1 \le c_i \le 10^{6}$

Note: as in subtask 4, the hierarchy can be very deep, see the note there on how to increase the stack size.

Examples

Input:

1
6 8
-1 0 0 1 2 2 1 1
3 4 3 5 6 7
1 1 0 0 1 1
1 1 3 2 2 1

Output:

Case #0: 2

Comment:

To submit for this subtask, please log in.

Don’t hesitate to ask us any question about this task, programming or the website via email (info@soi.ch).

Alpine Echoes

After a long hike through the Swiss Alps, Mouse Stofl has finally fallen asleep. Unfortunately, the annual Mouse Bell Festival is about to begin in the nearby valleys.

The festival has $N$ bells, numbered from $0$ to $N-1$ , spread across $G$ valleys, numbered from $0$ to $G-1$ . Bell $i$ has base loudness $a_i$ and is located in valley $v_i$ .

Sound echoes between the mountains, so bells in the same valley amplify each other. Valley $g$ has an echo factor $b_g$ . The loudness of a ringing bell is its base loudness multiplied by the echo factor of its valley and by the number of bells ringing in its valley. The total loudness is the sum of the loudnesses of all ringing bells.

For example, suppose that bells with base loudnesses $1$ , $4$ and $7$ ring in a valley with echo factor $2$ . Since three bells are ringing, each of them is multiplied by $2\cdot3=6$ , so together they have loudness $6+24+42=72$ . If the bell with base loudness $7$ is muffled, only two bells ring in this valley. Each of them is multiplied by $2\cdot2=4$ , and the valley is only $4+16=20$ loud.

Initially, all bells are ringing. Mouse Binna does not want the festival to wake Stofl. She has exactly $K$ wool covers. Each cover completely muffles one bell: a muffled bell makes no sound and does not count as ringing.

Help Binna to find the minimum possible total loudness after she muffles exactly $K$ bells.

Input and Output

All subtasks use the same input and output format.

Input

The first line contains the number of test cases $T$ . $T$ test cases follow, each in the following format:

The first line contains three integers $N$ , $G$ , and $K$ ; the number of bells, the number of valleys, and the number of wool covers.
The second line contains $G$ integers $b_{0}, b_{1}, \ldots, b_{G-1}$ , the echo factors of the valleys.
The third line contains $N$ integers $a_{0}, a_{1}, \ldots, a_{N-1}$ , the base loudnesses of the bells.
The fourth line contains $N$ integers $v_{0}, v_{1}, \ldots, v_{N-1}$ , where $v_i$ is the valley containing bell $i$ .

Output

For every $0\le t<T$ , output a line Case #t: L, where $L$ is the minimum possible total loudness in test case $t$ after muffling exactly $K$ bells.

Subtask 1: One Valley (8 points)

In this subtask, we have $G=1$ .

Limits

$T=100$ .
The sum of $N$ over all test cases does not exceed $22\,000\,000$ .
$1\le N\le 2'700\,000$ .
$G=1$ .
$0\le K\le N$ .
$1\le a_i\le 1\,000$ for every $0\le i<N$ .
$1\le b_g\le 1\,000$ for every $0\le g<G$ .
$0\le v_i<G$ for every $0\le i<N$ .
Every valley contains at least one bell.

These limits guarantee that the loudness of every possible choice of muffled bells fits in a signed 64-bit integer.

Example

Input:

Output:

Case #0: 36
Case #1: 24

Comment:

Case #0: Binna muffles the bells with base loudnesses

7

and

4

. The three remaining bells are each multiplied by

2\cdot3=6

, so the total loudness is

6\cdot(1+2+3)=36

Case #1: Binna muffles the bell with base loudness

8

. The three remaining bells are each multiplied by

1\cdot3=3

, so the total loudness is

3\cdot(1+5+2)=24

To submit for this subtask, please log in.

Subtask 2: Lonely Bells (11 points)

In this subtask, we have $G=N$ . Since every valley contains at least one bell, every valley contains exactly one bell.

Limits

$T=100$ .
The sum of $N$ over all test cases does not exceed $5'500\,000$ .
$1\le N\le 2'700\,000$ .
$G=N$ .
$0\le K\le N$ .
$1\le a_i\le 1\,000$ for every $0\le i<N$ .
$1\le b_g\le 1\,000$ for every $0\le g<G$ .
$0\le v_i<G$ for every $0\le i<N$ .
Every valley contains at least one bell.

These limits guarantee that the loudness of every possible choice of muffled bells fits in a signed 64-bit integer.

Example

Input:

Output:

Case #0: 11
Case #1: 8

Comment:

Case #0: Every bell rings alone in its valley, so its loudness is its base loudness times the echo factor of its valley. The five bells have loudnesses

1\cdot2=2

4\cdot2=8

7\cdot8=56

2\cdot3=6

and

3\cdot1=3

. Binna muffles the two loudest bells, with loudnesses

56

and

8

, which leaves a total loudness of

2+6+3=11

Case #1: All echo factors are

1

. Binna muffles the bell with base loudness

8

, which leaves a total loudness of

1+5+2=8

To submit for this subtask, please log in.

Subtask 3: Identical Bells (22 points)

This year, all bells were cast by the same bell maker, and all valleys have exactly the same shape. So all bells have the same base loudness, and all valleys have the same echo factor. However, different valleys may still contain different numbers of bells.

Limits

$T=100$ .
The sum of $N$ over all test cases does not exceed $5'500\,000$ .
$1\le N\le 2'700\,000$ .
$1\le G\le N$ .
$0\le K\le N$ .
$1\le a_i\le 1\,000$ for every $0\le i<N$ , and $a_{0}=a_{1}={\dots}=a_{N-1}$ .
$1\le b_g\le 1\,000$ for every $0\le g<G$ , and $b_{0}=b_{1}={\dots}=b_{G-1}$ .
$0\le v_i<G$ for every $0\le i<N$ .
Every valley contains at least one bell.

These limits guarantee that the loudness of every possible choice of muffled bells fits in a signed 64-bit integer.

Example

Input:

2
7 3 2
3 3 3
2 2 2 2 2 2 2
0 1 1 2 2 2 2
6 2 2
1 1
1 1 1 1 1 1
0 1 1 1 1 1

Output:

Case #0: 54
Case #1: 10

Comment:

Case #0: Valley

0

contains one bell, valley

1

contains two bells, and valley

2

contains four bells. Binna muffles two bells in valley

2

. Then one bell rings in valley

0

, with loudness

3\cdot1\cdot2=6

, and two bells ring in each of valleys

1

and

2

, each with loudness

3\cdot2\cdot2=12

. The total loudness is

6+4\cdot12=54

Case #1: Four bells keep ringing. It would be best to have two of them ringing in each valley, but valley

0

only contains one bell. So Binna muffles two bells in valley

1

. Then one bell rings in valley

0

with loudness

1

, and three bells ring in valley

1

, each with loudness

3

. The total loudness is

1+3\cdot3=10

To submit for this subtask, please log in.

Subtask 4: Medium Festival (16 points)

In this subtask, we have $N\le 2\,000$ .

Limits

$T=100$ .
The sum of $N$ over all test cases does not exceed $200\,000$ .
$1\le N\le 2\,000$ .
$1\le G\le N$ .
$0\le K\le N$ .
$1\le a_i\le 1\,000$ for every $0\le i<N$ .
$1\le b_g\le 1\,000$ for every $0\le g<G$ .
$0\le v_i<G$ for every $0\le i<N$ .
Every valley contains at least one bell.

These limits guarantee that the loudness of every possible choice of muffled bells fits in a signed 64-bit integer.

Example

Input:

Output:

Case #0: 26
Case #1: 8

Comment:

Case #0: Three bells keep ringing. If one of them rings in valley

0

and two in valley

1

, the smallest possible total loudness is

32

. If two ring in valley

0

and one in valley

1

, it is

26

, and if all three ring in valley

0

, it is

72

. So the minimum is

26

: Binna leaves the bells with base loudnesses

1

and

4

ringing in valley

0

, which contributes

2\cdot2\cdot(1+4)=20

. She also leaves the bell with base loudness

2

ringing in valley

1

, which contributes

3\cdot1\cdot2=6

. The total loudness is therefore

20+6=26

Case #1: Binna muffles the bell with base loudness

8

. This leaves exactly one ringing bell in each valley, with total loudness

2+1+5=8

To submit for this subtask, please log in.

Subtask 5: Few Valleys (18 points)

In this subtask, we have $G\le 50$ .

Limits

$T=100$ .
The sum of $N$ over all test cases does not exceed $5'500\,000$ .
$1\le N\le 2'700\,000$ .
$1\le G\le 50$ .
$0\le K\le N$ .
$1\le a_i\le 1\,000$ for every $0\le i<N$ .
$1\le b_g\le 1\,000$ for every $0\le g<G$ .
$0\le v_i<G$ for every $0\le i<N$ .
Every valley contains at least one bell.

These limits guarantee that the loudness of every possible choice of muffled bells fits in a signed 64-bit integer.

To submit for this subtask, please log in.

Subtask 6: Full Festival (25 points)

There are no additional restrictions.

Limits

$T=100$ .
The sum of $N$ over all test cases does not exceed $5'500\,000$ .
$1\le N\le 2'700\,000$ .
$1\le G\le N$ .
$0\le K\le N$ .
$1\le a_i\le 1\,000$ for every $0\le i<N$ .
$1\le b_g\le 1\,000$ for every $0\le g<G$ .
$0\le v_i<G$ for every $0\le i<N$ .
Every valley contains at least one bell.

These limits guarantee that the loudness of every possible choice of muffled bells fits in a signed 64-bit integer.

To submit for this subtask, please log in.

Don’t hesitate to ask us any question about this task, programming or the website via email (info@soi.ch).

Fajitas

The mice are having a fajita evening. $N$ mice have gathered, and the pantry contains $M$ ingredients. Initially, the mice have $q_i$ units of ingredient $i$ in stock.

The mice cook after $1 \le K \le 2$ different recipes. Each mouse can eat fajitas of any recipe. Their objective is to eat as many fajitas as possible!

The evening lasts $D$ minutes. Each minute, every mouse does exactly one of the following:

Buy: Run to the shop and buy one unit of one ingredient of its choice. The unit is added to the stock and can be used from the same minute on. A mouse can buy any ingredient. After buying, they can’t eat in the same minute, as heating up the fajita is the main component of preparing it, and they come back too late for that.
Eat: Prepare and eat one fajita after one of the recipes. All needed ingredients are taken from the stock as it is at the end of the current minute. If several mice eat in the same minute, the stock must cover the required ingredients for all of them together.
Wait: Do nothing.

The shop never runs out of anything, and the stock is shared by all mice.

What is the maximum total number of fajitas the mice can eat?

Subtask 1: Plan a small dinner (18 points)

In this subtask, you are additionally given a target number $G$ , and instead of just claiming that eating $G$ fajitas is possible, you have to prove it: Output a complete schedule with which the mice eat at least $G$ fajitas.

Input

The first line contains the number of test cases $T$ . $T$ test cases follow, each in the following format:

The first line of each test case contains $N$ , $M$ , $D$ , $K$ , and $G$ — the number of mice, the number of ingredients, the number of minutes in the evening, the number of recipes, and the number of fajitas to be eaten.
The second line contains the $M$ stock values $q_{0}, q_{1}, \dots, q_{M-1}$ .
$K$ lines follow, the $k$ -th of them contains $M$ integers $r_{k,0}, r_{k,1}, \dots, r_{k,M-1}$ describing recipe $k$ : Recipe $k$ requires $r_{k,i}$ units of ingredient $i$ .

Output

For the $t$ -th test case, output a line “Case #t:”, followed by $D$ lines: The $d$ -th of which describes minute $d$ and contains $N$ space-separated actions, the $p$ -th of which describes the action of mouse $p$ . Each action can be one of the following:

E<k> — the mouse eats a fajita of recipe $k$ (e.g. E1)
B<i> — the mouse buys one unit of ingredient $i$ (e.g. B0),
. — the mouse waits.

Limits

$T = 25$
$1 \le N \le 2$
$1 \le M \le 2$
$1 \le D \le 4$
$1 \le K \le 2$
$0 \le q_i \le 2$
$0 \le r_{k,i} \le 2$ , each recipe uses at least one ingredient
$G$ is the maximum number of fajitas that can be eaten.

Example

Input:

Output:

Case #0:
B0 B0
E0 E0
E0 .

Comment:

In the first minute, both mice buy one unit of ingredient

0

, so together with the initial stock there are

3

units in stock afterwards. In the second minute both mice eat (using

2

of the

3

units), and in the third minute one mouse eats a fajita, using up the last unit. There is no schedule with which the mice eat more than

3

fajitas.

To submit for this subtask, please log in.

Subtask 2: Short dinners (13 points)

From now on, output only the maximum total number of fajitas eaten. All mice use the same recipe ( $K = 1$ ).

Input

The first line contains the number of test cases $T$ . $T$ test cases follow, each in the following format:

The first line of each test case contains $N$ , $M$ , $D$ , and $K$ — the number of mice, the number of ingredients, the number of minutes in the evening, and the number of recipes.
The second line contains the $M$ stock values $q_{0}, q_{1}, \dots, q_{M-1}$ .
$K$ lines follow, the $k$ -th of them contains $M$ integers $r_{k,0}, r_{k,1}, \dots, r_{k,M-1}$ describing recipe $k$ : Recipe $k$ requires $r_{k,i}$ units of ingredient $i$ .

Output

For the $t$ -th test case, output a single line “Case #t: X”, where $X$ is the maximum total number of fajitas eaten.

Limits

$T = 100$
$K = 1$
$1 \le N \le 200$
$1 \le D \le 200$
$1 \le M$ , and the sum of $M$ over all test cases is at most $1000$ .
$0 \le q_i \le 10^{12}$
$0 \le r_{k,i} \le 1000$ , each recipe uses at least one ingredient

Example

Input:

Output:

Case #0: 2
Case #1: 3

Comment:

In the first test case, the dinner only lasts one minute. If one mouse runs to the shop to buy an additional ingredient of type

1

, the remaining two mice will have enough ingredients to eat one fajita each.

The second test case is the schedule from the subtask 1 example.

To submit for this subtask, please log in.

Subtask 3: Huge Dinners (25 points)

Same as subtask 2, but the dinner can last much longer, many more mice show up, and the pantry holds many more ingredients.

Limits

$T = 100$
$K = 1$
$1 \le N \le 2.5 \cdot 10^{5}$
$1 \le D \le 2.5 \cdot 10^{5}$
$1 \le M$ , and the sum of $M$ over all test cases is at most $2.5 \cdot 10^{5}$
$0 \le q_i \le 10^{12}$
$0 \le r_{k,i} \le 200$ , each recipe uses at least one ingredient

To submit for this subtask, please log in.

Subtask 4: Diverse Meal (12 points)

Mouse Stofl and his friend group are getting a bit bored of the same old recipe (“but it was what my grandparents did at home!”), and decided to get experimental. They got a cookbook (Easy Cooking, with at most $500$ ingredients!) and now have a second recipe! But they still want to eat as many fajitas as possible in total.

Limits

$T = 100$
$K = 2$
$1 \le N \le 500$
$1 \le D \le 500$
$1 \le M$ , and the sum of $M$ over all test cases is at most $500$
$0 \le q_i \le 10^{12}$
$0 \le r_{k,i} \le 1000$ , each recipe uses at least one ingredient

Example

Input:

Output:

Case #0: 5

Comment:

In this case, an optimal solution is to buy

7

units of ingredient

0

and then eat

3

fajitas using recipe

1

as well as

2

fajitas using recipe

0

resulting in a total of

5

fajitas eaten.

To submit for this subtask, please log in.

Subtask 5: The Ultimate Fajita Chef (Noémie) (32 points)

Actually, they found out that they did not like the new recipe that much. But fortunately, Mouse Noémie, the well-known chef, is also part of the group and proposes a complex recipe with more ingredients.

Limits

$T = 100$
$K = 2$
$1 \le N \le 2.5 \cdot 10^{5}$
$1 \le D \le 2.5 \cdot 10^{5}$
$1 \le M$ , and the sum of $M$ over all test cases is at most $5 \cdot 10^{4}$
$0 \le q_i \le 10^{12}$
$0 \le r_{k,i} \le 500$ , each recipe uses at least one ingredient

To submit for this subtask, please log in.

Don’t hesitate to ask us any question about this task, programming or the website via email (info@soi.ch).

Magic Forest

A group of $N$ people wants to cross a magic forest. The forest is dangerous, but there is a magic stone that protects everyone who touches it while crossing. At most $K$ people can touch the stone at the same time, so at most $K$ people can cross together. A group crossing together must walk as slowly as the slowest person in the group.

There is only one magic stone. Once a group has crossed, the stone is on the other side. To let more people cross, one or more people have to bring the stone back. Going back also takes the time of the slowest of them.

For each person $i$ you know the time $a_i$ it takes them to cross the forest alone. The input guarantees $a_{0}\le a_{1}\le \dots \le a_{N-1}$ .

Find the minimum total time until all $N$ people have crossed the forest.

Subtask 1: Two people at a time (7 points)

At most two people can touch the stone at the same time, i.e. $K = 2$ .

Input

The first line contains the number of test cases $T$ . $T$ test cases follow, each in the following format:

The first line of the test case contains $N$ , the number of people. The second line contains $N$ integers $a_{0}, a_{1}, \dots, a_{N-1}$ , the crossing times of the people.

Output

For the $t$ -th test case, output a line Case #t: X, where $X$ is the minimum amount of time needed for all people to cross the forest.

Limits

$T = 100$
$2 \le N \le 1\,000\,000$
$1 \le a_i \le 10^{5}$
$a_{0}\le a_{1}\le \dots \le a_{N-1}$

Example

Input:

1
4
1 2 5 10

Output:

Case #0: 17

Comment:

Persons

0

and

1

cross (

2

time units), then person

0

returns (

1

time unit). Persons

2

and

3

cross together (

10

time units), then person

1

returns (

2

time units). Finally persons

0

and

1

cross again (

2

time units). The total time is

2 + 1 + 10 + 2 + 2 = 17

To submit for this subtask, please log in.

Subtask 2: Small groups (8 points)

At most $K$ people can touch the stone at the same time, where $K$ is given in the input. There are at most $10$ people.

Input

The first line contains the number of test cases $T$ . $T$ test cases follow, each in the following format:

The first line of the test case contains $N$ and $K$ , the number of people and the maximum number of people that can touch the stone at the same time. The second line contains $N$ integers $a_{0}, a_{1}, \dots, a_{N-1}$ , the crossing times of the people.

Output

For the $t$ -th test case, output a line Case #t: X, where $X$ is the minimum amount of time needed for all people to cross the forest.

Limits

$T = 100$
$2 \le N \le 10$
$2 \le K \le N$
$1 \le a_i \le 10^{5}$
$a_{0}\le a_{1}\le \dots \le a_{N-1}$

Example

Input:

1
4 3
1 2 5 10

Output:

Case #0: 13

Comment:

Persons

0

and

1

cross (

2

time units), then person

0

returns (

1

time unit). Finally persons

0

2

and

3

cross (

10

time units). The total time is

2 + 1 + 10 = 13

To submit for this subtask, please log in.

Subtask 3: Medium groups (15 points)

At most $K$ people can touch the stone at the same time. There are at most $100$ people.

Input

The first line contains the number of test cases $T$ . $T$ test cases follow, each in the following format:

Output

For the $t$ -th test case, output a line Case #t: X, where $X$ is the minimum amount of time needed for all people to cross the forest.

Limits

$T = 150$
$2 \le N \le 100$
$2 \le K \le N$
$1 \le a_i \le 10^{5}$
$a_{0}\le a_{1}\le \dots \le a_{N-1}$

Example

Input:

1
4 3
1 2 5 10

Output:

Case #0: 13

Comment:

Persons

0

and

1

cross (

2

time units), then person

0

returns (

1

time unit). Finally persons

0

2

and

3

cross (

10

time units). The total time is

2 + 1 + 10 = 13

To submit for this subtask, please log in.

Subtask 4: Large groups – partial scoring (40 points)

At most $K$ people can touch the stone at the same time. There are at most $10\,000$ people.

Your task is to output any valid schedule that gets all people across. The better your total time, the more points you get.

Scoring

For each test case, we compute the relative error $e = \frac{X - OPT}{OPT}$ between your schedule time $X$ and the optimal time $OPT$ . Each test case is assigned a quality score $q$ based on its error:

Optimal schedule ( $X = OPT$ ): $q = 100\%$
Suboptimal schedule ( $X > OPT$ ): $q$ caps at 90% and scales down to 0%:
- An error of $0.0001\%$ ( $e \le 10^{-6}$ ) or better gives $q = 90\%$ .
- An error of $10\%$ ( $e \ge 0.1$ ) or worse gives $q = 0\%$ .
- In between, $q$ scales logarithmically: every factor of $10$ improvement adds $18\%$ .

Examples for quality $q$ :

Error = 1% ( $e = 10^{-2}$ ): 1 factor of 10 better than 10% $\rightarrow$ $q = 18\%$
Error = 0.01% ( $e = 10^{-4}$ ): 3 factors of 10 better than 10% $\rightarrow$ $q = 54\%$
Error = 0.0001% ( $e = 10^{-6}$ ): 5 factors of 10 better than 10% $\rightarrow$ $q = 90\%$

Subtask Score:

Your total score for the subtask is computed from the average quality across all test cases:

\text{Subtask Score} = 90\% \cdot \text{avg}(q) + \begin{cases} 10\% & \text{if all test cases are optimal} \\ 0\% & \text{otherwise} \end{cases}

If any schedule is invalid, the subtask gives $0$ points.

Input

The first line contains the number of test cases $T$ . $T$ test cases follow, each in the following format:

Output

For the $t$ -th test case, output a line Case #t: X U, where $X$ is the total time of your schedule and $U$ is the number of trips. Then output $U$ lines describing the trips in order. Each line has the form

V --> p1 p2 ...

for a trip from the left side to the right side, or

V <-- p1 p2 ...

for a trip from the right side back to the left side. $V$ is the number of people in the trip and $p1, p2, {\dots}$ are their indices ( $0$ -indexed).

Limits

$T = 200$
$2 \le N \le 10\,000$
$2 \le K \le N$
$1 \le a_i \le 10^{5}$
$a_{0}\le a_{1}\le \dots \le a_{N-1}$

Example

Input:

1
4 2
1 2 5 10

Output:

Case #0: 17 5
2 --> 0 1
1 <-- 0
2 --> 2 3
1 <-- 1
2 --> 0 1

Comment:

This is the optimal schedule from Subtask 1 with total time

17

To submit for this subtask, please log in.

Subtask 5: Many paths – partial scoring (30 points)

The forest contains $M$ different paths. The magic stone can be carried along any of them, but each path is different: some paths are more dangerous than others, so on path $i$ the stone can protect at most $k_i$ people at once. Moreover, the paths have different lengths. A group crossing path $i$ needs $b_i \cdot (\text{slowest person in the group})$ time units. Every path can be traversed in both directions. It is guaranteed that at least one path can protect $2$ or more people.

There is still only one stone, so only one path can be used at a time.

Your task is to output any valid schedule that gets all people across. The better your total time, the more points you get.

The scoring is the same as in Subtask 4, except that the quality score $q$ is:

Optimal schedule ( $X = OPT$ ): $q = 100\%$
Suboptimal schedule ( $X > OPT$ ): $q$ caps at 90% and scales down to 0%:
- An error of $0.001\%$ ( $e \le 10^{-5}$ ) or better gives $q = 90\%$ .
- An error of $100\%$ ( $e \ge 1$ ) or worse gives $q = 0\%$ .
- In between, $q$ scales logarithmically: every factor of $10$ improvement adds $18\%$ .

Input

The first line contains the number of test cases $T$ . $T$ test cases follow, each in the following format:

The first line of the test case contains $N$ and $M$ , the number of people and the number of paths. The second line contains $N$ integers $a_{0}, a_{1}, \dots, a_{N-1}$ , the crossing times of the people. The third line contains $M$ integers $k_{0}, k_{1}, \dots, k_{M-1}$ , the maximum number of people the stone can protect on each path. The fourth line contains $M$ integers $b_{0}, b_{1}, \dots, b_{M-1}$ , the length factors of the paths.

Output

V P --> p1 p2 ...

for a trip from the left side to the right side using path $P$ , or

V P <-- p1 p2 ...

for a trip from the right side back to the left side using path $P$ . $V$ is the number of people in the trip, $P$ is the path index ( $0$ -indexed), and $p1, p2, {\dots}$ are the people crossing.

Limits

$T = 200$
$2 \le N \le 100$
$1 \le M \le 100$
$1 \le k_i \le N$
at least one $k_i \ge 2$
$1 \le b_i \le 10^{5}$
$1 \le a_i \le 10^{5}$
$a_{0}\le a_{1}\le \dots \le a_{N-1}$

Example

Input:

Output:

Case #0: 9 3
2 0 --> 0 1
1 0 <-- 0
2 1 --> 0 2

Comment:

Path

0

can protect

2

people and has factor

1

; path

1

can protect

2

people and has factor

2

. Persons

0

and

1

cross using path

0

(

1 \cdot 2 = 2

time units), then person

0

returns using path

0

(

1 \cdot 1 = 1

time unit). Finally persons

0

and

2

cross using path

1

(

2 \cdot 3 = 6

time units). Total time is

9

This schedule is valid but not optimal: using path

0

for the last trip as well gives total time

6

To submit for this subtask, please log in.

Don’t hesitate to ask us any question about this task, programming or the website via email (info@soi.ch).

Explorer's Tree

Mouse Binna is a legendary explorer. Long ago she traveled through a region with $N$ sites, numbered $0$ to $N-1$ . All we have from that time is an old book, which contains some of the rules that every explorer must follow, together with a record of her trip.

In the book, we can see that the sites are connected by one-way routes. For each site the book records a circular order of its neighbors, i.e. the sites the explorer can reach with a direct route. While exploring the neighbors, an explorer must follow this circular order, but may begin at any neighbor they like. So if the book records $(2, 1, 3)$ for a site, they can go through its neighbors as $2, 1, 3$ , as $1, 3, 2$ or as $3, 2, 1$ , but not as $2, 3, 1$ .

Binna started at site $S$ . At every site with at least one neighbor she picked one of them to begin with, and then went through all of that site’s neighbors in the circular order recorded in the book. Each new site she came to she explored right away; the ones she had already visited she skipped. Formally, when $d_A$ is the number of neighbors of site $A$ and $t_A$ the index of the neighbor Binna began with:

explore(A):
    mark A as visited
    for i = 0, 1, ..., d[A] - 1:
        B = the neighbor of A at index ((t[A] + i) mod d[A])
        if B is not visited yet:
            explore(B)

The whole trip is the single call explore(S).

When Binna first arrived at a site $B$ other than $S$ , she came there from some site. The book records that site as $p_B$ , and for the start site it records $p_S = -1$ . Together these $N$ numbers $p_{0}, p_{1}, \ldots, p_{N-1}$ describe the Explorer’s Tree.

Subtask 1: Following the book (10 points)

Here the book also tells you which neighbor Binna began with at every site. Work out the Explorer’s Tree.

Input

The first line contains the number of test cases $T$ . Each test case looks like this:

The first line contains NNN, MMM and SSS: the number of sites, the number of
routes, and the site Binna started at.
The next NNN lines contain the circular orders, one for each site in order
from 000 to N−1N-1N−1.  The line for site iii contains did_idi​, the number of one-way routes from site iii,
followed by did_idi​ integers vi,0,…,vi,di−1v_{i,0}, \ldots, v_{i,d_i-1}vi,0​,…,vi,di​−1​: the neighbors of
site iii, in circular order.
The last line contains NNN integers t0,…,tN−1t_{0}, \ldots, t_{N-1}t0​,…,tN−1​: the index of the
neighbor Binna began with at each site.  If di=0d_i = 0di​=0 then ti=0t_i = 0ti​=0,
otherwise 0≤ti<di0 \le t_i < d_i0≤ti​<di​.

Output

For the $k$ -th test case, output a line “Case #k:”, followed on the same line by $N$ integers $p_{0}, \ldots, p_{N-1}$ : the Explorer’s Tree. Test cases are numbered from $0$ to $T-1$ in all subtasks.

Limits

$T = 100$
$1 \le N \le 200$
$N-1 \le M \le 1000$
$0 \le S < N$
$d_{0}+ d_{1}+ \ldots + d_{N-1} = M$
$0 \le v_{i,j} < N$ and $v_{i,j} \ne i$ : no route from a site to itself
the neighbors of one site are all different: at most one route from $A$ to $B$
every site can be reached from $S$ , so Binna visits all of them

Example

Input:

2
4 4 0
3 2 1 3
1 2
0
0
1 0 0 0
6 9 3
1 4
1 0
2 4 5
3 0 1 5
0
2 2 3
0 0 0 2 0 1

Output:

Case #0: -1 0 1 0
Case #1: 3 3 5 -1 2 3

Comment:

Case #0: Site

0

has the circular order

(2, 1, 3)

and

t_{0}= 1

, so Binna goes through its neighbors in the order

1

3

2

. She explores site

1

, whose only neighbor is site

2

, so that is explored next. Back at site

0

, she explores site

3

. The last neighbor of site

0

is site

2

, already visited, so it is skipped. Sites

1

and

3

were therefore first reached from site

0

, and site

2

from site

1

Case #1: Binna starts at site

3

, which has the circular order

(0, 1, 5)

and

t_{3}= 2

, so she goes through its neighbors in the order

5

0

1

. She explores site

5

first. Site

5

has

t_{5}= 1

, so she looks at site

3

, which is already visited, and then explores site

2

; from site

2

she explores site

4

. Back at site

3

, sites

0

and

1

are explored in turn, and the single neighbor each of them offers is already visited by then.

To submit for this subtask, please log in.

Subtask 2: Ancestors and descendants only (14 points)

From here on the book does not say which neighbors Binna began with. Instead it gives the Explorer’s Tree. Decide whether her trip could have produced exactly that Explorer’s Tree, that is, whether there is a choice of starting neighbors that leads to it.

In this subtask, for every $A$ and $B$ , between which there is a route, one of the two sites is an ancestor of the other in the Explorer’s Tree. The ancestors of a site $Y \ne S$ are $p_Y$ , then $p_{p_Y}$ , then $p_{p_{p_Y}}$ , and so on up to $S$ . The start site $S$ has no ancestors.

Input

The same as in Subtask 1, except for the last line of a test case. Instead of the starting neighbors it contains $N$ integers $0 \le p_{0}, \ldots, p_{N-1} < N$ which describe the Explorer’s Tree. You can rely on all of this:

$p_S = -1$
every other site $B$ is a neighbor of $p_B$
starting at any site $Y$ and repeatedly moving to its parent will finally reach $S$

These input guarantees also apply to Subtasks 3–6. The restriction that every route connects an ancestor and a descendant applies only to Subtask 2.

Output

For the $k$ -th test case, output a line “Case #k: YES” if the starting neighbors can be chosen so that Binna’s trip produces exactly this Explorer’s Tree, and “Case #k: NO” otherwise.

Limits

$T = 100$
$1 \le N \le 1000$
$N-1 \le M \le 1000$
$0 \le S < N$
$d_{0}+ d_{1}+ \ldots + d_{N-1} = M$
$0 \le v_{i,j} < N$ and $v_{i,j} \ne i$ : no route from a site to itself
the neighbors of one site are all different: at most one route from $A$ to $B$
every site can be reached from $S$ , so Binna visits all of them

Example

Input:

Output:

Case #0: YES
Case #1: NO

Comment:

Case #0: At site

0

, if Binna begins with neighbor

1

, she goes through the list as

1

3

2

. She explores

1

, and from there

2

. Back at

0

she explores

3

, and her last neighbor

2

is already visited. This gives exactly the Explorer’s Tree in the input.

Case #1: At site

0

there are four ways to go around

(3, 1, 4, 2)

, and none of them gives the tree in the input. Beginning with

3

makes

p_{3}= 0

instead of

1

, and beginning with

4

makes

p_{4}= 0

instead of

2

. Beginning with

1

gets

1

and

3

right, but then reaches

4

straight from

0

, so

p_{4}= 0

instead of

2

. Beginning with

2

fails the same way with

3

To submit for this subtask, please log in.

Subtask 3: Two routes too many (15 points)

Input and output as in Subtask 2. In this subtask, exactly two routes are not part of the Explorer’s Tree.

Limits

$T = 100$
$4 \le N \le 1000$
$M = N + 1$
$0 \le S < N$
$d_{0}+ d_{1}+ \ldots + d_{N-1} = M$
$0 \le v_{i,j} < N$ and $v_{i,j} \ne i$ : no route from a site to itself
the neighbors of one site are all different: at most one route from $A$ to $B$
every site can be reached from $S$ , so Binna visits all of them

Example

Input:

2
6 7 0
1 1
2 2 3
1 4
1 5
1 5
1 0
-1 0 1 1 2 3
6 7 0
1 1
2 2 3
1 4
1 5
1 5
1 4
-1 0 1 1 2 3

Output:

Case #0: YES
Case #1: NO

Comment:

Case #0: The two routes that are not part of the Explorer’s Tree are the ones from

4

5

and from

5

0

. At site

1

, if Binna begins with neighbor

3

, she explores

3

and right away

5

, whose only neighbor

0

is already visited. Back at

1

she explores

2

and right away

4

, whose only neighbor

5

is already visited. This gives exactly the Explorer’s Tree in the input.

Case #1: The two routes that are not part of the Explorer’s Tree are the ones from

4

5

and from

5

4

. If Binna begins with neighbor

2

at site

1

, she explores

2

, right away

4

, and then

5

, so

5

cannot be a child of

3

. If she begins with

3

, she explores

3

, right away

5

, and then

4

, so

4

cannot be a child of

2

To submit for this subtask, please log in.

Subtask 4: A star-shaped tree (20 points)

Input and output as in Subtask 2. In this subtask, the Explorer’s Tree is a star: $p_B = S$ for every site $B \ne S$ .

Limits

$T = 100$
$1 \le N \le 4 \cdot 10^{5}$
$N-1 \le M \le 8 \cdot 10^{5}$
$0 \le S < N$
$d_{0}+ d_{1}+ \ldots + d_{N-1} = M$
$0 \le v_{i,j} < N$ and $v_{i,j} \ne i$ : no route from a site to itself
the neighbors of one site are all different: at most one route from $A$ to $B$
every site can be reached from $S$ , so Binna visits all of them

Example

Input:

Output:

Case #0: NO
Case #1: YES

Comment:

Case #0: Whichever of

1

2

and

3

Binna visits first, that site has exactly one neighbor, and that neighbor has not been visited yet, so she explores it from there. Its entry in the Explorer’s Tree would then be that site instead of

0

, which the input does not allow.

Case #1: At site

0

, if Binna begins with neighbor

3

, she goes

3

1

2

. Site

3

has no neighbors; site

1

only has

3

, which is already visited; site

2

has none either. So all three are reached straight from

0

, which is what the input asks for.

To submit for this subtask, please log in.

Subtask 5: Few neighbors per site (24 points)

Input and output as in Subtask 2. In this subtask, every site has at most $10$ neighbors.

Limits

$T = 100$
$1 \le N \le 4 \cdot 10^{5}$
$N-1 \le M \le 8 \cdot 10^{5}$
$d_i \le 10$ for every site $i$
$0 \le S < N$
$d_{0}+ d_{1}+ \ldots + d_{N-1} = M$
$0 \le v_{i,j} < N$ and $v_{i,j} \ne i$ : no route from a site to itself
the neighbors of one site are all different: at most one route from $A$ to $B$
every site can be reached from $S$ , so Binna visits all of them

Example

Input:

2
7 10 0
2 1 2
3 3 6 4
1 5
1 6
1 5
1 0
1 4
-1 0 0 1 1 2 3
7 10 0
2 1 2
3 3 4 6
1 5
1 6
1 5
1 0
1 4
-1 0 0 1 1 2 3

Output:

Case #0: YES
Case #1: NO

To submit for this subtask, please log in.

Subtask 6: No constraints (17 points)

Input and output as in Subtask 2. In this subtask, there are no further constraints.

Limits

$T = 100$
$1 \le N \le 4 \cdot 10^{5}$
$N-1 \le M \le 8 \cdot 10^{5}$
$0 \le S < N$
$d_{0}+ d_{1}+ \ldots + d_{N-1} = M$
$0 \le v_{i,j} < N$ and $v_{i,j} \ne i$ : no route from a site to itself
the neighbors of one site are all different: at most one route from $A$ to $B$
every site can be reached from $S$ , so Binna visits all of them

Example

Input:

2
25 35 0
12 1 2 3 4 5 6 7 8 9 10 11 12
1 13
1 14
1 15
1 16
1 17
1 18
1 19
1 20
1 21
1 22
1 23
1 24
1 12
1 1
1 2
1 3
0
1 5
1 6
1 7
1 8
1 9
1 10
1 11
-1 0 0 0 0 0 0 0 0 0 0 0 0 1 2 3 4 5 6 7 8 9 10 11 12
25 36 0
12 1 2 3 4 5 6 7 8 9 10 11 12
1 13
1 14
1 15
1 16
1 17
1 18
1 19
1 20
1 21
1 22
1 23
1 24
1 12
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
-1 0 0 0 0 0 0 0 0 0 0 0 0 1 2 3 4 5 6 7 8 9 10 11 12

Output:

Case #0: YES
Case #1: NO

To submit for this subtask, please log in.

Don’t hesitate to ask us any question about this task, programming or the website via email (info@soi.ch).

Rohrpost

Mouse Stofl has been elected mayor of Potsdam. His entire campaign ran on a single slogan:

Postdam – Rohrpost Delivers All Mice

and with it he promised two things: to rename the city to Postdam, and to build a Rohrpost to finally give it a functioning public transport system made for mice.

Renaming the city was the easy part. This being Germany, there is an established and documented process for it (§ 9(1) BbgKVerf). Stofl filed the forms on day one and paid 1.15 euros in processing fees. After just 1’456 of his 1’461 days in office, the name change was officially confirmed. Building the Rohrpost is harder, so Stofl needs your help.

A Rohrpost is a network of underground tubes through which capsules are propelled by compressed air from so-called machine stations. This technology for the future of urban mobility has been demonstrated to work in a proof of concept in which almost 8 million shipments a year were delivered over a 400 km network. This experiment from 1865 became known as Berlin’s Rohrpost and was so successful that it ran for over a hundred years. The Postdam capsules will be bigger and better, and they are designed to deliver mice.

Postdam consists of $N$ intersections, numbered $0$ to $N-1$ , connected by $N-1$ roads. The $i$ -th road connects the intersections $a_i$ and $b_i$ , and a mouse needs $w_i$ minutes to walk along it; we call $w_i$ the walking time of the road. Between any two intersections there is exactly one route.

Stofl can lay tubes along some of the roads; a road with a tube along it is called a tubed road. Capsules inside the tubes are so fast that a ride in one takes $0$ minutes. The compressed air only works if the whole system is one piece, so the tube network must be connected: It must be possible to get from every tubed road to every other tubed road using tubed roads only. A mouse may enter and leave the tube network at any intersection along it.

The travel time between two intersections is the total walking time along the route between them, where every tubed road on that route takes $0$ minutes. The $D$ in Stofl’s slogan also stands for a delivery guarantee: His election poster promises that the travel time between every pair of intersections is at most $D$ minutes. He did not commit to an exact $D$ , but he claimed it would be “as small as the d in Postdam”, and, as he keeps his promises, he needs $D$ to be as small as possible. For a given tube network, $D$ is the largest travel time between any two intersections.

An intersection at which exactly one tubed road ends is a terminal of the tube network, and we say that the network branches at an intersection where three or more tubed roads meet. A tube network with exactly two terminals is a single tube line.

Instead of listing every tubed road, you describe a tube network by its terminals: $M$ distinct intersections $u_{0},{\dots},u_{M-1}$ . The network then consists of all roads that lie on the route between some pair of them, that is, the smallest connected network containing all of them. Every nonempty tube network has a unique set of terminals, so each $u_j$ you print must be a terminal of the resulting network, and not an intersection inside it. You may list the terminals in any order.

Stofl’s campaign promised the mice at least two terminal stations, so $M\ge 2$ . He promised his voters a Rohrpost, so he has to build one – even where the best $D$ is already reached without laying a single tube.

In every subtask, test cases are numbered from $0$ to $T-1$ .

Subtask 1: Thinking about the first tube line (6 points)

Stofl is thinking about where to put the first tube line. If he places it along the route between the intersections $u_{0}$ and $u_{1}$ , what is $D$ once that line is in service?

Input

The first line contains the number of test cases $T$ . The $T$ test cases follow in the following format:

The first line contains the number of intersections $N$ .
The second line contains the two ends $u_{0}$ and $u_{1}$ of the tube line.
$N-1$ lines follow, the $i$ -th of them containing $a_i$ , $b_i$ and $w_i$ .

Output

For the $t$ -th test case, output a line “Case #t:” followed by a single integer, the value of $D$ .

Limits

$T=100$ .
$2 \le N \le 10^{5}$ .
$0 \le a_i,b_i < N$ and $a_i \ne b_i$ for all $0 \le i < N-1$ .
$1 \le w_i \le 10^{9}$ for all $0 \le i < N-1$ .
$0 \le u_{0},u_{1}< N$ and $u_{0}\ne u_{1}$ .

Example

Input:

Output:

Case #0: 7

Comment:

Case #0: The three roads on the route from

0

4

each get a tube. The slowest pair is then

1

and

5

: three minutes to intersection

2

, no time at all through the tubes to intersection

3

, and four more minutes to

5

To submit for this subtask, please log in.

Subtask 2: Longer is not always better (13 points)

Stofl has been staring at his first tube line all night and is now convinced that the best line is the one that runs along a longest route: That way, the two intersections that are furthest apart are helped the most.

Show him that this is wrong. You are given the road network without walking times, and you choose the walking times yourself. Call a route longest if no other route has a larger total walking time. Assign a walking time to every road such that every longest route, tubed on its own, gives a strictly larger $D$ than the smallest $D$ that any tube line achieves. For some road networks no such assignment exists; in that case, say so.

Input

The first line contains the number of test cases $T$ . The $T$ test cases follow in the following format:

The first line contains the number of intersections $N$ .
$N-1$ lines follow, the $i$ -th of them containing $a_i$ and $b_i$ .

Output

For the $t$ -th test case: If such walking times exist, output a line “Case #t: Possible” followed by a line with $N-1$ integers, where the $i$ -th of them is the walking time you assign to the $i$ -th road. Otherwise output a single line “Case #t: Impossible”.

Any assignment with the required property is accepted.

Limits

$T=100$ .
$2 \le N \le 10^{4}$ .
$0 \le a_i,b_i < N$ and $a_i \ne b_i$ for all $0 \le i < N-1$ .
The walking times you output must satisfy $1 \le w_i \le 10^{9}$ .

Example

Input:

Output:

Case #0: Impossible
Case #1: Possible
2 3 3 4 3 2 1 2 1

Comment:

Case #0: There is a single road, so there is only one route and only one possible tube line. No choice of walking times can make a longest route worse than the best line.

Case #1: The nine numbers are the walking times for the nine roads, in the order the roads are given. With them there are two longest routes, from

4

6

and from

4

8

, both taking

11

minutes, and tubing either one leaves

D=8

. Tubing the route from

6

8

instead leaves only

D=7

, so neither longest route is the best tube line.

To submit for this subtask, please log in.

Subtask 3: Find the best line (26 points)

Stofl now has to decide for real. He still builds a single tube line, that is, a tube network with two terminals. Which line makes $D$ as small as possible?

Input

As in subtask 1, except that the second line of every test case (the one with $u_{0}$ and $u_{1}$ ) is missing.

Output

For the $t$ -th test case, output a line “Case #t: D M” where $D$ is the best (that is, smallest) delivery guarantee that a single tube line achieves and $M=2$ is the number of terminals of your tube line. Then output a line with the two intersections, separated by a space.

If multiple tube lines achieve $D$ , you may output any of them. The $D$ you print must be the one your own network achieves.

Limits

$T=100$ .
$2 \le N \le 10^{5}$ .
$0 \le a_i,b_i < N$ and $a_i \ne b_i$ for all $0 \le i < N-1$ .
$1 \le w_i \le 10^{9}$ for all $0 \le i < N-1$ .
Your answer must satisfy $M=2$ , and the two intersections must be different.

Example

Input:

Output:

Case #0: 6 2
4 5

Comment:

Case #0: Tubing the route from

4

5

leaves the roads at intersection

2

untubed, so the slowest pair is

0

and

1

with

D=3+3=6

. Note that

0

4

is a longest route, taking

9

minutes, but tubing it would leave

D=7

To submit for this subtask, please log in.

Subtask 4: One machine station (16 points)

The city council approves the Rohrpost, but the budget stretches to exactly one machine station. All the compressed air comes from there, so the tube network may branch at no more than one intersection – the machine station itself. The tube network has at most $K$ terminals.

Input

As in subtask 3, except that the first line of every test case contains $N$ and $K$ .

Output

For the $t$ -th test case, output a line “Case #t: D M” where $D$ is the best (that is, smallest) delivery guarantee that such a tube network achieves and $M$ is the number of terminals of your tube network. Then output a line with those $M$ intersections, separated by spaces. Your answer must satisfy $2 \le M \le K$ , and the $M$ intersections must be pairwise distinct. In addition, your tube network must branch at no more than one intersection.

If multiple tube networks achieve $D$ , you may output any of them. The $D$ you print must be the one your own network achieves.

Limits

$T=100$ .
$2 \le N \le 10^{5}$ .
$0 \le a_i,b_i < N$ and $a_i \ne b_i$ for all $0 \le i < N-1$ .
$1 \le w_i \le 10^{9}$ for all $0 \le i < N-1$ .
$2 \le K \le N$ .

Example

Input:

Output:

Case #0: 3 3
0 4 5
Case #1: 2 2
0 1

Comment:

Case #0: The machine station stands at intersection

3

, with lines to

4

, to

5

and through

2

0

. Only intersection

1

is left out, at three minutes from the network, so

D=3

. Tubing every road would need a network that branches at

2

and at

3

, which is not allowed here.

Case #1: Here the Rohrpost cannot help at all: Whichever roads Stofl tubes, two of the four outer intersections are still two minutes apart, so

D=2

either way. He has to build one anyway, so the answer still needs two terminals; tubing the single road from

0

1

is one way.

To submit for this subtask, please log in.

Subtask 5: More machine stations (18 points)

After the first capsule crosses Postdam in under a minute, the city council approves a supplementary budget and Stofl buys more machine stations. The tube network may now branch at any number of intersections, but tubes are not free: it still has at most $K$ terminals, and $K$ is now small.

Input and Output

As in subtask 4, except that the tube network may branch at any number of intersections.

Limits

$T=100$ .
$2 \le N \le 10^{5}$ .
$0 \le a_i,b_i < N$ and $a_i \ne b_i$ for all $0 \le i < N-1$ .
$1 \le w_i \le 10^{9}$ for all $0 \le i < N-1$ .
$2 \le K \le \min(N,20)$ . This is the special restriction for this subtask; subtask 4 allows $K$ up to $N$ .

Example

Input:

Output:

Case #0: 0 4
0 1 4 5

Comment:

Case #0: This is the same input as in subtask 4, but the answer is better: The network may now branch at intersection

2

and at intersection

3

, so every road can be tubed with only four terminals and no mouse has to walk at all.

To submit for this subtask, please log in.

Subtask 6: Rohrpost Reloaded (21 points)

The Rohrpost was a big success. Stofl is re-elected, and even the city signs have arrived, finally making the renaming complete. The city council has also approved an expansion of the network: The number of terminals $K$ can now be up to $N$ , and the limits for $N$ have been extended too. Everything else is as in subtask 5.

Input and Output

As in subtask 5.

Limits

$T=100$ .
$2 \le N \le 10^{6}$ .
$0 \le a_i,b_i < N$ and $a_i \ne b_i$ for all $0 \le i < N-1$ .
$1 \le w_i \le 10^{9}$ for all $0 \le i < N-1$ .
$2 \le K \le N$ .

Grading

Since we can’t ensure that optimized brute-force solutions or heuristics won’t be able to pass, we will manually check all submissions and may retroactively give an accepted submission 0 points.

We expect a solution that runs in $\mathcal O(N \cdot (\log(N \cdot w_{\max}))^c)$ for a constant $c$ , where $w_{\max}$ is the largest walking time. See Introduction to Algorithm Design for an explanation of the $\mathcal O$ -notation.

To submit for this subtask, please log in.

Don’t hesitate to ask us any question about this task, programming or the website via email (info@soi.ch).

Grader Practice

The grader practice for the second round consists of 4 tasks, each of which is worth 25 points. You can gain a maximum of 100 points counting towards your second-round score.

This helps you get familiar with our grading system which we will use in all our events after the second round, including workshops, camp, finals, and team selection.

You can submit in C++ (recommended), Java or Python.

C++:	If you don’t have a setup already, we recommend installing VSCode.
Java:	Read Java on the SOI Grader.
Python:	Read Python on the SOI Grader.

For the grader practice, you can discuss solutions with friends or publicly on Discord, as long as you don’t share source code. We are also happy to help you! If you need help with the grading system or have questions regarding the theory or tasks, don’t hesitate to ask here or in Discord.

Don’t hesitate to ask us any question about this task, programming or the website via email (info@soi.ch).

Junior Ranking

Rank	Username	Total (700)	tablegr… (100) tablegroups	microwa… (100) microwaving	standemehr (100)	alpinee… (100) alpineechoes	fajitas (100)	magicfo… (100) magicforest	graderp… (100) graderpractice
	loading ...

Regular Ranking

Rank	Username	Total (700)	standemehr (100)	alpinee… (100) alpineechoes	fajitas (100)	magicfo… (100) magicforest	explorer (100)	rohrpost (100)	graderp… (100) graderpractice
	loading ...