DMPG '18 G6 - Class Chitchat

View as PDF

Submit solution

Points: 20 (partial)
Time limit: 1.8s
Memory limit: 512M

Problem type

There are N students in your school conveniently labelled from 1 to N. You are person 1. There are C classes numbered 1 to C, and student i takes c_i different classes. It is guaranteed that every student takes at least one class, although some classes may not have any students.

Two students are able to communicate if and only if they share a class. Additionally, some pairs of people get along more easily than others. Each student has a friend value v_i. Then it costs |v_i-v_j|+K for student i to deliver a message to student j where K is fixed for any two students who are able to directly communicate with each other.

The cost required to deliver a message to student i is the sum of the costs from each direct communication. For each i, you would like to know the minimum cost required for you, student 1, to deliver a message to student i.


For all subtasks:

1 \le v_i \le 1\,000\,000

1 \le c_i

Subtask 1 [20%]

1 \le N, C \le 400

0 \le K \le 1\,000\,000

Subtask 2 [30%]

1 \le N, C \le 100\,000

N \le c_1+c_2+\dots+c_N \le 200\,000


Subtask 3 [50%]

1 \le N, C \le 100\,000

N \le c_1+c_2+\dots+c_N \le 200\,000

0 \le K \le 1\,000\,000

Input Specification

The first line contains three space-separated integers, N, C, and K.
The next line contains N space-separated integers, the i^\text{th} of which is v_i.
The following N lines contain c_i+1 space-separated integers. The first number is c_i and the indices of the c_i classes which student i is taking follow.

Output Specification

Output N lines, each containing a single integer. On the i^\text{th} line, write the minimum cost required to communicate with student i. If it is not possible to communicate with student i, print -1. Answers are guaranteed to fit within a 64-bit integer.

Sample Input

9 10 7
18 5 6 11 17 19 2 14 5
2 1 7
5 5 2 3 1 10
1 5
2 1 2
2 7 6
1 4
2 3 6
1 10
1 10

Sample Output



There are no comments at the moment.