MEC '16 P4 - Circuitry

View as PDF

Submit solution

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

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 N parts.

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

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 N (1 \le N \le 500) and M (N-1 \le M \le \frac{N(N-1)} 2), representing the number of parts and steps specified in the blueprint.

The next M lines each represent one step of the blueprint. Each line contains three space separated integers A_i, B_i (1 \le A_i, B_i \le N) and L_i (1 \le L_i \le 10^5), representing a connection between parts A_i and B_i using a wire of length L_i.

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

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.


  • 1
    Kirito  commented on March 13, 2021, 4:30 a.m. edited

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