## DMOPC '15 Contest 6 P4 - Line Graph

View as PDF

Points: 10 (partial)
Time limit: 1.0s
Memory limit: 128M

Author:
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

The minimum spanning tree of a graph is defined as a tree which contains all the vertices, and does so using the smallest accumulative weight of edges.

You are given a graph in the shape of a line: it has vertices and edges, where the -th edge connects vertices and , using weight . You are also given an integer : there exist an arbitrary number of "network trampolines," indicating that a weightless edge connects the -th vertex to the -th vertex, given that both exist, for all values of . You are also allowed to use the other existing edges as necessary.

All edges are undirected.

Find the minimum spanning tree of the graph by outputting the sum the weights of all encompassed edges.

#### Input Specification

On the first line, there will be the integer , followed by a space, followed by the integer .

On the next line, there will be space-separated integers representing where the -th integer, from to , connects the -th vertex with the -th vertex. (It should be assumed that the vertices are numbered from to .)

For all cases, . For all from to , .

For 35% of the points:

For another 20% of the points:

For all remaining cases:

#### Output Specification

Print a single integer, the combined weight of the graph's minimum spanning tree.

#### Sample Input 1

3 2
3 5

#### Sample Output 1

3

#### Explanation for Sample 1

There are three vertices in this graph. 1 and 2 are connected by an edge of weight 3, 2 and 3 by one of weight 5, and it can be deduced that, since and , 1 and 3 are connected by an edge of weight 0. The minimum spanning tree consists of the 0-weight edge and the 3-weight edge, which spans all the vertices.

#### Sample Input 2

5 2
5 6 7 8

#### Sample Output 2

5

#### Explanation for Sample 2

There are five edges: edges of weight 0 exist from 1 to 3, 3 to 5, and 2 to 4. Take all of these edges, along with the edge connecting 1 and 2, and the minimum spanning tree is complete.

#### Sample Input 3

5 3
5 6 7 8

#### Sample Output 3

11

• commented on Nov. 27, 2018, 3:52 p.m. edit 2

• commented on Jan. 17, 2017, 12:00 p.m.

Typo in the Sample Input 1 Explanation:

1 and 2 are connected by and edge of weight 3

• commented on Jan. 17, 2017, 3:04 p.m.

Fixed. Thank you for pointing that out!

• commented on March 3, 2016, 5:44 p.m. edit 2

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