MEC '16 P4 - Circuitry

View as PDF

Submit solution

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

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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 then 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 \leq N \leq 500) and M (N - 1 \leq M \leq {N(N - 1) \over 2}), representing the amount 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 \leq A_i, B_i \leq N) and L_i (1 \leq L_i \leq 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.


  • 0
    jeffreyxiao  commented on March 28, 2016, 9:10 a.m. edit 2


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

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

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

      so so, the problem statement has been fixed.

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

    • -1
      atarw  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