## MEC '16 P4 - Circuitry

View as PDF

Points: 15 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type

In an alternate universe where circuits are not cyclic, SoundwaveSuperior's project members had to work on an engineering project due the next day! They were given a blueprint which detailed the assembly of a circuit with parts.

The blueprint contained steps which instructed the reader on how to assemble the circuit. Each step specified two parts and , which were to be connected with a wire of length .

Being smart students, they noticed that the blueprint was inefficient as it used a greater amount of wire to connect all components than what was needed. Therefore, in an attempt to conserve wire supplies, they decided to ignore some of the steps in the blueprint and follow the rest (such that all parts of the circuit are connected using minimum total wire length).

However, SoundwaveSuperior realized that there could be many combinations of steps that they could follow that would give them the minimum total wire length. Since his group members are lazy, your task is to help him determine which steps he has to follow and which ones he can ignore.

#### Input Specification

On one line, two space separated integers and , representing the number of parts and steps specified in the blueprint.

The next lines each represent one step of the blueprint. Each line contains three space separated integers , and , representing a connection between parts and using a wire of length .

#### Output Specification

For each step of the blueprint, output useful if the step has to be followed no matter how the circuit is configured, so so if the step only has to be followed for some circuit arrangements, or not useful if the step can always be ignored.

#### Sample Input

4 5
1 2 5
2 3 2
2 4 2
3 4 1
1 3 4

#### Sample Output

not useful
so so
so so
useful
useful

#### Explanation of Sample Output

The minimum length of wire needed to connect all parts is 7. To achieve this, steps 4 and 5 must always be followed, and step 1 can always be ignored. Steps 2 and 3 could be followed, depending on the circuit arrangement, but it is not guaranteed that they will be followed for all optimal circuit arrangements.

• commented on March 12, 2021, 11:30 p.m. edited

Additional test cases have been added, courtesy of Plasmatic and d, and all out-of-contest submissions have been rejudged.

• commented on March 26, 2016, 11:41 p.m.

are we supposed to output so so or so-so?

• commented on March 26, 2016, 11:56 p.m.

so so, the problem statement has been fixed.

• commented on March 25, 2016, 5:09 p.m.
not useful
so so
so so
useful
useful
• commented on March 25, 2016, 5:25 p.m. edited

Yes, you’re right. I think I changed the order of the sample input before the contest and forgot to change the output. Fixed the sample output + explanation