(Challenge) Codechef War II

All submissions for this problem are available.
### Read problem statements in [Hindi](http://www.codechef.com/download/translated/JULY19/hindi/CHFWAR2.pdf), [Bengali](http://www.codechef.com/download/translated/JULY19/bengali/CHFWAR2.pdf), [Mandarin Chinese](http://www.codechef.com/download/translated/JULY19/mandarin/CHFWAR2.pdf), [Russian](http://www.codechef.com/download/translated/JULY19/russian/CHFWAR2.pdf), and [Vietnamese](http://www.codechef.com/download/translated/JULY19/vietnamese/CHFWAR2.pdf) as well. Chefland is a country with $N$ cities (numbered $1$ through $N$) and $M$ bidirectional roads (numbered from $1$ through $M$). Each road connects two different cities and no two different roads connect the same pair of cities. Bitland declared war on Chefland and after multiple battles, all roads of Chefland have ended up in a very bad state. Moreover, the war is causing psychological damage to the citizens of Chefland — for each valid $u$, the *noneagerness* of the inhabitants of city $u$ on day $d$ is $E_u(d) = P_u + Q_u \cdot d$. In Chefland, there are $K$ special cities that are very important strategically. Ada, the queen of Chefland, decided to repair some roads and construct new roads in such a way that if any one of these roads is destroyed, it is still possible to reach each special city from any other special city using only the roads that were repaired or constructed. It is allowed to work on repairing and constructing different roads simultaneously, but to keep Chefland stable, Ada ordered that on each day, the number of roads that are being repaired and/or constructed must be at most $S$. Also, whenever we start repairing or constructing a road, the work on that road cannot be paused until the road is finished. The earliest day on which we can start repairing or constructing a road is day $1$; let's denote the last day on which we finish repairing or constructing a road by $T$. The queen does not want to wait too much, so for each day between $1$ and $T$ inclusive, there must be at least one road which is currently being constructed or repaired. Note that this means $T$ cannot exceed the time it would take to repair and construct all roads. For each valid $i$, the $i$th of the original roads connected cities $U_i$ and $V_i$, its length was $L_i$ kilometres and the cost of repairing it is described by two parameters $A_i$ and $B_i$. The workers of Chefland can only repair one kilometer of road per day and it is not allowed to work on different parts of a road at the same time, so it takes exactly $L_i$ days to repair this road. If we start repairing this road on day $d$, it costs $A_i + B_i \cdot d$. For each pair of different cities $u$ and $v$, let's denote the length of the shortest path between these cities before the original roads were damaged (before Chefland's invasion) by $D_{u, v}$. Then, it takes $D_{u, v}$ days to construct a brand new road between the cities $u$ and $v$. This road does not pass through any cities other than $u$ and $v$. If we start constructing this road on day $d$, it costs $(E_u(d)+E_v(d)) \cdot D_{u, v}$. It is not allowed to construct a road between two cities if they are already directly connected by a road or if they were originally directly connected by a road. Help Ada design a plan that minimises the total cost. Formally, determine which roads should be repaired, which ones should be constructed and for each of these roads, determine the day on which the work on this road should start. The total cost of this plan should be as small as possible, while all other constraints must be satisfied perfectly. ### Input  The first line of the input contains four spaceseparated integers $N$, $M$, $K$ and $S$.  The second line contains $K$ spaceseparated integers denoting the indices of the special cities.  $N$ lines follow. For each $i$ ($1 \le i \le N$), the $i$th of these lines contains two spaceseparated integers $P_i$ and $Q_i$.  $M$ more lines follow. For each $i$ ($1 \le i \le M$), the $i$th of these lines contains five spaceseparated integers $U_i$, $V_i$, $L_i$, $A_i$ and $B_i$. ### Output  First, print a line containing a single integer $X$ denoting the number of roads you want to repair.  Then, print $X$ lines. Each of these lines should contain two spaceseparated integers $d$ and $e$ denoting that you want to start repairing road $e$ on day $d$.  Next, print a line containing a single integer $Y$ denoting the number of new roads you want to construct.  Then, print $Y$ lines. Each of these lines should contain three spaceseparated integers $d$, $u$ and $v$ denoting that you want to start building a road between cities $u$ and $v$ on day $d$. ### Constraints  $2 \le K \le N = 2^8$  $2^4 = S \le M \le (N \cdot (N1))/2$  $1 \le U_i, V_i \le N$ for each valid $i$  $1 \le L_i \le 2^{12}$ for each valid $i$  $1 \le A_i, B_i \le 2^8$ for each valid $i$  $1 \le P_i, Q_i \le 2^{11}$ for each valid $i$ ### Example Input ``` 7 9 3 2 1 3 7 1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 2 1 1 1 1 4 1 1 2 2 3 1 1 3 2 4 1 1 4 3 4 1 1 5 3 5 1 1 6 3 6 1 1 7 5 7 1 1 8 6 7 1 1 9 ``` ### Example Output ``` 8 1 1 2 2 3 3 4 5 5 6 6 7 7 8 8 9 0 ``` ### Scoring The score of each test case (and therefore each test file) is the sum of costs of all the roads you want to repair or construct. The score of a submission is the sum of scores of all test files. Your goal is to minimise the score of your submission. There are sixteen test files. If your program gets a nonAC verdict on any test file, your submission's verdict will be nonAC. In other words, an AC verdict denotes that your program runs successfully on all the test files. ### Test Generation In all test cases, $N = 2^8$ and $S = 2^4$. There are two types of original road networks:  Type I: There is a road between each pair of cities and the special cities are chosen uniformly randomly.  Type II: First, ten permutations $p_1, p_2, \ldots, p_{10}$ of integers $1$ through $K+K/2$ ($1$indexed) are generated. For each valid $i$ and $j$, the edge between cities $p_{i, j}$ and $p_{i, j+1}$ is added if it did not exist. Then, edges are added uniformly randomly until the total number of edges reaches $\left\lfloor\frac{N \cdot (N1)}{5} \right\rfloor$. The special cities are chosen uniformly randomly between 1 and $K+K/2$. After generating the road network, the indices of the cities are relabelled. A permutation $q$ of numbers from $1$ through $N$ is uniformly randomly chosen, the new index of city $u$ will be $q_u$. If in the original network cities $u$ and $v$ are connected, in the final network cities $q_u$ and $q_v$ are connected. $K$ is either $N/4$ or $N/2$. Next, we choose two parameters $MIN_L$ and $MAX_L$: either $1$ and $2^{12}$ respectively or $2^{11}10$ and $2^{11}+10$ respectively. Next, we choose two more parameters $MIN_A$ and $MAX_A$: either $1$ and $2^8$ respectively or $2^7  20$ and $2^7 + 20$ respectively. The lengths of all roads are chosen uniformly randomly between $MIN_L$ and $MAX_L$ inclusive. All parameters $A_i$ and $B_i$ are chosen uniformly randomly between $MIN_A$ and $MAX_A$ inclusive. All parameters $P_i$ and $Q_i$ are chosen uniformly randomly between $8 \cdot MIN_A$ and $8 \cdot MAX_A$ inclusive. There is a test file for each unique combination of the following four parameters: road network type, $K$, the pair $(MIN_L, MAX_L)$ and the pair $(MIN_A, MAX_A)$.Author:  alei 
Tags  alei 
Date Added:  18062019 
Time Limit:  4 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, SQL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions