P16344 [USTC Guochuang Cup Junior 2026] Construction Problem

Subtask 0 uses community testdata, and Subtask 1 uses official testdata.

You need to construct a directed acyclic graph (DAG) with $n$ vertices and $m$ edges **without multiple edges** (vertices are numbered starting from $1$). The in-degree of vertex $1$ and the out-degree of vertex $n$ must both be $0$. Also, for every integer $i$ in $0 \sim p$, it must be possible to keep only some directed edges in the graph so that the number of distinct paths from vertex $1$ to vertex $n$ is exactly $i$. Please output the DAG you constructed, and for each $i$, specify which edges need to be kept. The answer is not unique, so you only need to output any feasible solution. See the output format for details. You may choose the values of $n$ and $m$ yourself, but you must ensure $n \le 24, m \le 65$. > A path $P$ from vertex $1$ to vertex $n$ that passes through $|P|$ vertices can be described as a sequence of length $|P|$, $(P_1, P_2, \dots, P_{|P|})$, where $P_1 = 1, P_{|P|} = n$, and for $i = 1, 2, \dots, |P| - 1$, the graph contains a directed edge $P_i \to P_{i+1}$. > Two paths $A, B$ are different if and only if $|A| \ne |B|$, or there exists a positive integer $i$ in $1 \sim |A|$ such that $A_i \ne B_i$.

The input contains only one line with a positive integer $p$.

- On the first line, output two positive integers $n, m$, representing the number of vertices and edges in the DAG you construct. - On the next $m$ lines, on the $i$-th line output two positive integers $u, v$, representing the $i$-th directed edge $u \to v$ in the graph. - On the next $p+1$ lines, on the $i$-th line output a string of length $m$ consisting only of `0` and `1`, indicating which edges to keep in order to make the number of distinct paths from vertex $1$ to vertex $n$ equal to $i-1$. From left to right, the $j$-th character is `1` if the $j$-th edge is kept, and `0` otherwise.

#### Sample Explanation In the sample, $p = 3$. The figure on the next page shows a feasible graph constructed by the sample output.  When none of the six edges are selected, vertex $1$ obviously cannot reach vertex $5$, so the number of paths is $0$. When only edges $1$ and $2$ are kept, there is only one path from vertex $1$ to vertex $5$ ($1 \to 2 \to 5$), so the number of paths is $1$. When edges $1, 2, 3, 4$ are kept, there are two paths from vertex $1$ to vertex $5$ ($1 \to 2 \to 5$ and $1 \to 3 \to 5$), so the number of paths is $2$. When all edges are kept, there are three paths from vertex $1$ to vertex $5$ ($1 \to 2 \to 5, 1 \to 3 \to 5$ and $1 \to 4 \to 5$), so the number of paths is $3$. Therefore, this construction is valid. #### Constraints For all testdata, it is guaranteed that $p \le 75000$. This problem has a total of twenty test points. For each test point, the input is known (see the table below). You will get the score for a test point only if your construction is valid and satisfies $n \le 24, m \le 65$. Otherwise, you will get no score for that test point. | Test Point ID | $p =$ | Test Point ID | $p =$ | Test Point ID | $p =$ | Test Point ID | $p =$ | | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | | $1$ | $5$ | $6$ | $300$ | $11$ | $6000$ | $16$ | $35000$ | | $2$ | $10$ | $7$ | $600$ | $12$ | $8000$ | $17$ | $45000$ | | $3$ | $20$ | $8$ | $1000$ | $13$ | $10000$ | $18$ | $55000$ | | $4$ | $50$ | $9$ | $2000$ | $14$ | $15000$ | $19$ | $65000$ | | $5$ | $100$ | $10$ | $4000$ | $15$ | $25000$ | $20$ | $75000$ | #### Friendly Reminder - When $p$ is large, the output size is large, so please use a proper way to output. You should also open the output file properly to prevent your computer from crashing. - A checker `checker.cpp` is provided for you to test whether your construction is valid. The provided checker is different from the one used in the final judging, and you do not need to care about its internal details. Please extract the file provided with this problem. - Extract `checker.cpp` to the folder where your program for this problem is located. Then right-click in that folder, choose “Open in Terminal”, and compile `checker.cpp` using the following command: `g++ checker.cpp -o checker -O2 -std=c++14` - Then test your output using the following command: `./checker construct.in construct.out` - After the command runs successfully, if your construction is valid, you will see `Accepted`. Otherwise, you will see `Wrong answer` and detailed error information. Translated by ChatGPT 5