DMOPC '15 Contest 6 P4 - Line Graph

View as PDF

Submit solution

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

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 N vertices and N-1 edges, where the i-th edge connects vertices i and i+1, using weight w_i. You are also given an integer K: there exist an arbitrary number of "network trampolines," indicating that a weightless edge connects the i-th vertex to the i+K-th vertex, given that both exist, for all values of i. 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 N, followed by a space, followed by the integer K.

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

For all cases, 1 \le K \le 100\,000. For all i from 1 to N-1, 0 \le w_i \le 1\,000.

Subtask 1

For 35% of the points: 2 \le N \le 12

Subtask 2

For another 20% of the points: 2 \le N \le 1\,001

Subtask 3

For all remaining cases: 2 \le N \le 100\,000

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


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 K=2 and 3-1=2, 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


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



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

    Edit: Nvm I'm just bad

  • 2
    leonchen0613  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

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

      Fixed. Thank you for pointing that out!

  • -13
    Flowright  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.