TLE '16 Contest 4 P4 - Christmas Tree Building

View as PDF

Submit solution


Points: 17 (partial)
Time limit: 2.0s
Memory limit: 256M

Author:
Problem type
Fax McClad and his Christmas tree (in progress).

Fax McClad, Croneria's most innovative bounty hunter, has been assigned by the Cronerian government to set up a Christmas tree.

Fax is given N pieces of tree, numbered from 1 to N. There are already M connections within the tree pieces, each connection i has a length of l_i and connects tree pieces u_i and v_i. It is guaranteed that there is no more than one path between any two tree pieces.

Fax needs to connect the tree pieces such that all of the tree pieces form a complete tree. In a complete tree, there is exactly one path between any two tree pieces. Each connection that Fax makes has a length of 1. Fax is allowed to choose whichever tree piece is the top.

There are two types of trees that Fax can build, which is signified by Q. The first type of tree (Q = 1) has the largest height possible, so that people can see it far away. The second type of tree (Q = 2) has the smallest height possible, since the tree might interfere with Cronerian airspace. The height of the tree is the largest distance from the top of the tree to any other tree piece.

Can you help Fax to determine what the height of his tree will be?

Constraints

2 \le N

0 \le M \le N-1

1 \le l_i \le 10^6

Subtask Points N M Q
1 5 N \le 100 M = 1 Q = 1 or 2
2 10 N \le 100 M = N-1 Q = 1 or 2
3 15 N \le 100 No additional constraints Q = 1 or 2
4 25 N \le 10^5 No additional constraints Q = 1
5 45 N \le 10^5 No additional constraints Q = 2

Input Specification

The first line of input will contain three space-separated integers, N, M, and Q.

M lines of input follow. The i^{th} line contains three space-separated integers, u_i, v_i, and l_i.

Output Specification

Output a single integer, the maximum height of the tree if Q = 1, or the minimum height of the tree if Q = 2.

Sample Input 1

4 2 1
1 2 4
1 3 6

Sample Output 1

11

Explanation for Sample Output 1

One possible solution is to let piece 2 to be the top of the tree and connect piece 4 to piece 3.

Sample Input 2

4 2 2
1 2 4
1 3 6

Sample Output 2

6

Explanation for Sample Output 2

One possible solution is to let piece 1 be the top of the tree and connect piece 4 to piece 2.


Comments


  • 0
    Kirito  commented on Oct. 28, 2017, 11:01 p.m.
    Exception in thread "main" java.lang.IllegalArgumentException: Comparison method violates its general contract!
        at java.util.ComparableTimSort.mergeHi(ComparableTimSort.java:866)
        at java.util.ComparableTimSort.mergeAt(ComparableTimSort.java:483)
        at java.util.ComparableTimSort.mergeForceCollapse(ComparableTimSort.java:422)
        at java.util.ComparableTimSort.sort(ComparableTimSort.java:222)
        at java.util.Arrays.sort(Arrays.java:1246)
        at ChristmasTreeBuilding.DFS2(ChristmasTreeBuilding.java:216)
        at ChristmasTreeBuilding.DFS2(ChristmasTreeBuilding.java:211)
        at ChristmasTreeBuilding.main(ChristmasTreeBuilding.java:291)

  • 1
    aeternalis1  commented on Oct. 28, 2017, 10:52 p.m.

    ...but lead is Pb, mercury is Hg and silver is Ag?


  • 18
    Kirito  commented on Jan. 23, 2017, 5:12 p.m.


  • -10
    imaxblue  commented on Dec. 24, 2016, 8:56 a.m.

    This comment is hidden due to too much negative feedback. Click here to view it.


    • 20
      thomas0115  commented on Dec. 25, 2016, 12:41 p.m.

      Clearly the problems aren't the same since you solved Dreaming but not this (during the contest).


  • 1
    gloomcore  commented on Dec. 23, 2016, 6:45 p.m.

    Should tree be just the binary tree? Or any type of tree is acceptable?


    • 4
      d  commented on Dec. 23, 2016, 6:51 p.m.

      Any type of tree is acceptable.