Power Distribution

View as PDF

Submit solution

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

Author:
Problem type

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 the 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^\text{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^\text{th} of which represents the minimum length of wire needed to supply power to all houses for the j^\text{th} case.

Constraints

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

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

Sample Output

4
1

Explanation

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


Comments

There are no comments at the moment.