Ah, I could have used the PROBLEM LINK:Author: Full name Tester: Full name Editorialist: Full name DIFFICULTY:CAKEWALK, SIMPLE, EASY, MEDIUM or HARD. Intermediate levels like SIMPLEEASY, EASYMEDIUM, MEDIUMHARD are also possible. PREREQUISITES:Greedy, DP, Math etc. Ideally with the links to Wikipedia PROBLEM:QUICK EXPLANATION:Let's call the endpoints of additional edges "keypoint"s. The topology of keypoints form a cycle, so we can handle distance queries of keypoints quickly. For a general query, let's say it's from vertex $v_1$ on cycle $c_1$ to vertex $v_2$ on cycle $c_2$. The path goes through some keypoint $k_1$ on cycle $c_1$ and some $k_2$ on cycle $c_2$. Since every cycle has at most $2$ keypoints, we enumerate $k_1$ and $k_2$, and thus answer queries on constant time. EXPLANATION:Subtask 1This is a shortest path problem on a graph with $M=A_1+A_2+\dots+A_N$ vertices and $M+1$ edges. We can run Dijkstra's Algorithm for each query. The time complexity for heapoptimized Dijkstra's Algorithm is $O(M\log M)$. So total complexity is $O(QM\log M)$. Subtask 2Querying on one cycleConsider the easier problem: you have one cycle and you want to answer distance queries. Let's number the vertices $1,2,\dots,N$, and suppose the cycle is $123\dotsN1$. For any $i,j(i < j)$, the only simple paths between $i,j$ are:
Let's precompute $d_i$ as the length of path $1\to 2\to\dots\to i$. Then $l_1=d_jd_i$. Since $l_2+l_1$ is the length of the whole cycle, $l_2$ can be easily calculated, too. We return the smaller number between $l_1$ and $l_2$, and answer the query in $O(1)$ time. Querying on keypointsLet's call the endpoints of additional edges "keypoint"s. Consider how to answer distance queries between keypoints. We construct a new graph $C$ whose vertices are only the keypoints. For two keypoints:
The resulting graph $C$ is a cycle: every vertex has degree $2$ and $C$ is connected. Thus we can easily handle distance queries on $C$. Also, $C$ preserves distances on the original graph. So we can answer distance queries about endpoints in $O(1)$ time. The final solutionFirst, using the above algorithms we can support distance queries on one cycle and on keypoints. Suppose there is a query $(V_1,C_1,V_2,C_2)$. Since $C_1\ne C_2$, their shortest path must pass through some keypoint in cycle $C_1$, suppose it's $k_1$; it also passes through some keypoint in cycle $C_2$, say $k_2$. Then the shortest path has length $dis(V_1,k_1)+dis(k_1,k_2)+dis(k_2,V_2)$, and the smallest this value among all $(k_1,k_2)$'s is the answer. The three $dis()$'s can be obtained in $O(1)$ time. Each cycle has at most $2$ keypoints, so there are at most $4$ pairs of $(k_1,k_2)$ that we need to enumerate. The time complexity is $O(Q+M)$, where $M=A_1+A_2+\dots+A_N$. AUTHOR'S AND TESTER'S SOLUTIONS:Author's solution can be found [here][333]. Tester's solution can be found [here][444]. RELATED PROBLEMS:[333]: The link is provided by admins after the contest ends and the solutions are uploaded on the CodeChef Server. [444]: The link is provided by admins after the contest ends and the solutions are uploaded on the CodeChef Server asked 22 Aug '17, 20:25
