Power Distribution

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 0.6s
Memory limit: 64M

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

After years of combing through the archive of the Ancients, Phoenix1369 has finally found an interesting problem for the Don Mills Programming Club:

Given the x-coordinates of N houses arranged in a row, some of which can generate their own power, output the minimum length of electrical wire required to connect every home to a source of power, either directly or indirectly.

Input Specification

The first line of the input contains an integer T denoting the number of test cases.

The first line of a case contains an integer N, denoting number of homes arranged in a line.

The next N lines of a case each contain 2 space-separated integers: x_i and p_i (1 \le i \le N) denoting the x-coordinate of the i^{th} house, and whether it generates its own power, respectively.

Output Specification

Output T lines, each containing a single integer on a line by itself, the j^{th} of which represents the minimum length of wire needed to supply power to all houses for the j^{th} case.


1 \le T \le 10

1 \le x_1 < x_2 < \dots < x_N \le 10^9

p_i \in [ 0, 1 ]

It is guaranteed that at least one home will be able to generate its own electricity.

Subtask #1 [30%]

1 \le N \le 1000

Subtask #2 [70%]

1 \le N \le 10^5

Sample Input

1 1
2 0
5 0
1 1
8 0
9 1

Sample Output



In the first case, wires can be added between houses #1 and #2 and houses #2 and #3 for a total length of 1 + 3 = 4. House #3 gets power because it is indirectly connected to house #1 (via house #2).

In the second case, house #2 is the only house which requires power. Since it is closer to house #3, the length of the wire required is 9 - 8 = 1.

Original Problem Author: admin2; Problem Resource: Codechef


There are no comments at the moment.