Woburn Challenge 2017-18 Round 3 - Senior Division

Problem 4: Relevant Results

You own a group of N (1 ≤ N ≤ 400,000) webpages dedicated solely to the art of dynamic programming. Each page i includes links to K_i (0 ≤ K_i < N) other distinct pages, the j-th of which is page L_{i, j} (1 ≤ L_{i, j} ≤ N). The total number of links (Σ K_1..N) is at most 400,000. You consider a given page b to be "accessible" from a given page a if it's possible to follow a sequence of 0 or more links starting from page a and ending at page b.

Unfortunately, your pages aren't getting as much traffic as you'd like. It's clear that the most promising way of encouraging more people to come across your pages is to somehow cause them to appear earlier in the search results when someone searches for "dynamic programming" on the internet's most popular search engine.

Each page is assigned an integral "relevancy score" for a given search query such as "dynamic programming", and pages with higher scores then appear earlier in the results for that query. Page i's initial relevancy score is R_i (1 ≤ R_i ≤ 10⁹). Fortunately, if you donate C_i (1 ≤ C_i ≤ 10⁴) dollars to the search engine company, you can increase page i's score by 1! You can choose to do so 0 or more times for any page.

You're not yet sure about how much money you'd like to spend on helping to make your pages "more relevant", so you'll consider a series of M (1 ≤ M ≤ 400,000) independent questions. For the i-th question, you'd like to determine the minimum amount of money you'd need to spend in order to make all N of your pages "accessible" from search results with relevancy scores no smaller than Q_i (1 ≤ Q_i ≤ 10⁹). In other words, after you finish increasing all of the pages' scores as necessary, for each page b (1 ≤ b ≤ N), there must exist at least one page a such that page a's final relevancy score is greater than or equal to Q_i and page b is accessible from page a. Note that all M questions are independent, with changes to pages' scores not carrying over between them.

Subtasks

In test cases worth 9/38 of the points, N ≤ 2000, Σ K_1..N ≤ 2000, and M = 1.
In test cases worth another 15/38 of the points, M = 1.

Input Format

The first line of input consists of a single integer, N.
N lines follow, the i-th of which consists of three space-separated integers, R_i, C_i, and K_i, followed by K_i more integers L_{i, 1..Ki}, for i = 1..N.
The next line consists of a single integer, M.
M lines follow, the i-th of which consists of a single integer, Q_i, for i = 1..M.

Output Format

Output M lines, the i-th of which should consist of a single real number, the minimum cost (in dollars) required such that all N pages are accessible from search results with relevancy scores no smaller than Q_i.

Sample Input

5
9 3 1 4
11 1 0
8 2 1 1
4 2 1 3
7 2 1 2
3
10
12
1

Sample Output

9
18
0

Sample Explanation

If page 1's relevancy score is increased to 10 (for a cost of $3) and page 5's relevancy score is also increased to 10 (for a cost of $6), then all 5 pages will be reachable from search results with relevancy scores no smaller than 10. Pages 1, 2, and 5 will have sufficiently high relevancy score themselves, and page 1 links to page 4 which then links to page 3. This total cost of $9 is optimal.

All Submissions
Best Solutions

Point Value: 20 (partial)
Time Limit: 7.00s
Memory Limit: 128M
Added: Mar 23, 2018
Author: SourSpinach

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)