(Challenge) Building Anthills

All submissions for this problem are available.
### Read problem statements in [Hindi](http://www.codechef.com/download/translated/JAN20/hindi/ANTHILL.pdf), [Bengali](http://www.codechef.com/download/translated/JAN20/bengali/ANTHILL.pdf), [Mandarin Chinese](http://www.codechef.com/download/translated/JAN20/mandarin/ANTHILL.pdf), [Russian](http://www.codechef.com/download/translated/JAN20/russian/ANTHILL.pdf), and [Vietnamese](http://www.codechef.com/download/translated/JAN20/vietnamese/ANTHILL.pdf) as well. The queen of ants hired Ada to build their anthill. Ada designed the anthill as $N$ rooms (numbered $1$ through $N$) interconnected by $M$ bidirectional roads (numbered $1$ through $M$). For simplicity, let's denote a road that connects rooms $u$ and $v$ by $(u, v)$. At any time, there may be at most one road between any two rooms and roads connecting a room with itself are not allowed. Ada started from scratch by building the $N$ rooms and choosing the $M$ roads that should be built. In order to create the roads, she wants to give instructions to the ants and pay them in antcoins (a very small currency). There are two possible types of instructions: 1. $K$, $E = \{(x_1,y_1), (x_2,y_2), \ldots, (x_K,y_K)\}$: Let $E$ be a set of $K$ distinct roads. The ants should build all roads in the set $E$ that do not already exist. Moreover, for every three distinct rooms $u$, $v$ and $w$, if $(u, v) \in E$ and $(v, w) \in E$, then the ants should also build the road $(u, w)$ if it does not already exist. The cost of this instruction is $A \cdot K$ antcoins. 2. $u$, $v$: The ants should remove the road $(u, v)$ if it exists. The cost of this instruction is $R$ antcoins. After all the instructions are executed, only the planned $M$ roads should be built. Help Ada build the anthill while spending as few antcoins as possible. ### Input  The first line of the input contains four spaceseparated integers $N$, $M$, $A$ and $R$.  Each of the next $M$ lines contains two spaceseparated integers $u$ and $v$ denoting a road that connects rooms $u$ and $v$. ### Output First, print a line containing a single integer $Q$ ― the number of instructions. Then, print $Q$ lines; each of these lines should describe one instruction in the format `1 K x_1 y_1 x_2 y_2 ... x_K y_K` or `2 u v`. ### Test generation For all test files (except the example), $N=512$, $A=10$ and $R=2$. Next, internal parameters $S$, $L$ and $D$ are chosen in the following way:  $S$ and $L$ can be $1$ and $2,048$, $2$ and $1024$, $16$ and $256$, or $64$ and $128$.  $D$ can be $0$, $128$ or $2,048$.  There is one test file for each possible combination of these parameters. The anthill is then generated as follows:  $S$ sets of $L$ distinct roads are chosen uniformly randomly and independently (**In total $S \cdot L$ distinct roads are chosen**). The first instruction is executed $S$ times, once for each of these sets of roads.  Then, $D$ distinct existing roads are chosen uniformly randomly and independently. The second instruction is executed $D$ times, once for each of these roads. ### Scoring If any of your instructions are invalid, the sum of $K^2$ over all instructions of the first type exceeds $10^6$ or the number of instructions $Q \gt 10^6$, you will receive the Wrong Answer verdict. Otherwise, the score of a test file is the cost of constructing the anthill, i.e. the total number of antcoins paid to perform all instructions. 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 twelve test files. During the contest, the displayed score will account for exactly four test files, i.e. your score reflects your submission's performance on approximately 33.33% (4/12) of the test files. However, 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. After the end of the contest, your score will be changed to include the sum of your program's scores over the other 8 test files. ### Example Input ``` 4 5 10 2 1 2 2 3 3 4 4 1 1 3 ``` ### Example Output ``` 3 1 3 1 2 2 3 3 4 2 2 4 1 1 1 4 ```Author:  alei 
Editorial  https://discuss.codechef.com/problems/ANTHILL 
Tags  alei, alei, challenge, jan20, powergraphs, vijju123 
Date Added:  23122019 
Time Limit:  5 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
HELP
If you are still having problems, see a sample solution here. 