Mr. Biscuit is in trouble. He accidentally deleted all the programs in his server and his database is corrupted as a result. There was a graph contained in the database. The graph had a source node and the shortest paths from the source node to the other nodes was calculated using a function called SSSP. Mr. Biscuit has found the pseudocode of the function in his notebook. The pseudocode is given below:

```
Input: A weighted graph G with vertices V and edges E
procedure SSSP(G,source):
1 Let N ← number of nodes in G
2 Let D[] ← 100000000 // D is an one dimensional array of size N
3 D[source] = 0
4 for step from 1 to N
5 for all edges from (u,v) in E
6 if D[u] + cost[u][v] < D[v]
7 D[v] = D[u] + cost[u][v]
8 end if
9 end for
10 end for
11 return D
```

While running the function to achieve the result, the array $D$ was stored in the database after each iteration of the loop starting at line $4$. So, if the loop iterates $X$ times, the database will save $X$ copies of $D$, possibly with different values. Thus, after each iteration, the array $D$ may be updated with the information about the shortest path of each node from the source.

Now, the database has been corrupted and Mr. Biscuit has lost the results regarding the shortest paths of the nodes. He also lost the original graph, but remembers that none of the weights of the edges of that graph had an absolute value over $1000$. After a few days of relentless effort, he managed to salvage the values of all the indices of $D$ after each iteration of the loop. Mr. Biscuit has saved all these data in a temporary backup server. It could be the case that the shortest paths may be retrievable from the data that has been salvaged.

You will have to find if there exists shortest paths from the source node to all the other nodes in the original graph. For retrieving the result, you can perform some queries from the data that Mr. Biscuit has salvaged. Since the backup server has limited resources, you can only perform a limited number of such queries to make your decision correctly.

You can make three types of interactions in this problem:

$1$: The contestant will start the interaction by printing a $1$, the contestant will receive the value of $N$ as a response after this interaction. This type of interaction will occur only once at the start of the communication.

$2$ $t$ $i$ $j$ The contestant will ask for a sub-array from index $i$ to $j$ ($i<=j, 0 <= i, j, < N$) after the t’th ($1 <= t <= N$) iteration of the loop at line $4$ of the pseudocode. In response, the contestant will get the values from index $i$ to index $j$ of the array $D$ after the t’th iteration of the function SSSP. A contestant can make at most $2 * N$ interactions of this type. Each interaction should be valid.

3 result: After all the interactions of type $1$ and type $2$, a contestant will print the result in the last line of interaction. The result should be $1$, if there are shortest paths from the source to all the other nodes of the graph. Otherwise, the result should be $0$.

**Subtask #1 (10 points)**

$N = 1$

**Subtask #2 (10 points)**

$N = 2$

**Subtask #3 (25 points)**

$N = 3$

**Subtask #4 (55 points)**

$N <= 500$

After at most $2 * N$ queries of type $2$, you will have to answer $1$ if there exists shortest paths from the source node to all the other nodes in the original graph or $0$ otherwise. The result should be printed in the format mentioned in the interaction section. If you give an invalid query of any type, or if you request for an invalid query, you will receive a verdict of Wrong Answer.

For example, if $N = 3$, a sample interaction can be as follows:

input: 1

response: 3

input: 2 2 1 2

response: 7 12

input: 2 3 0 2

response: 0 7 12

input: 3 1

“Since this is an interactive problem, please don’t forget to flush your output after printing each line. You may use fflush(stdout) for printf/cout in C/C++, import sys and sys.stdout.flush() in Python to flush the output. If you use some other programming language, consult its documentation.

To learn more about Interactive Problems: https://help.toph.co/toph/interactive-problems” - reborn

In the pseudocode, the cost[u][v] indicates the weight of the directed edge connecting the nodes u and v.

Login to submit.

38%
Solution Ratio

mohanr7073Earliest,

mbsabbirr127Fastest, 0.0s

Um_nikLightest, 131 kB

steinumShortest, 515B

Toph uses cookies. By continuing you agree to our Cookie Policy.