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 Ki (0 ≤ Ki < N) other distinct pages, the j-th of which is page Li, j (1 ≤ Li, j ≤ N). The total number of links (Σ K1..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 Ri (1 ≤ Ri ≤ 109). Fortunately, if you donate Ci (1 ≤ Ci ≤ 104) 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 Qi (1 ≤ Qi ≤ 109). 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 Qi 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.
In test cases worth 9/38 of the points, N ≤ 2000, Σ K1..N ≤ 2000, and M = 1.
In test cases worth another 15/38 of the points, M = 1.
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, Ri, Ci, and Ki, followed by Ki more integers Li, 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, Qi, for i = 1..M.
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 Qi.
5 9 3 1 4 11 1 0 8 2 1 1 4 2 1 3 7 2 1 2 3 10 12 1
9 18 0
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.
Point Value: 20 (partial)
Time Limit: 7.00s
Memory Limit: 128M
Added: Mar 23, 2018
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3