CSES - Planets Queries II

Authors: Michael Cao, Benjamin Qi, Kevin Sheng

In this problem, we are given a functional graph and asked qq queries for the minimum distance between two vertices uu and vv.

Structure of the Graph

Notice that all functional graphs can be broken down into a bunch of "components". Each of these components consists of many trees directed towards the root, and a single cycle composed of said roots and some other nodes.

Here's an example of a possible "component". The trees are circled in red:

func graph

Given this, we can essentially break down each query into three cases:

Both in Tree

If both uu and vv are in a tree, we first have to get the distance from each node to the cycle. This can be precalculated for all nodes with BFS.

First of all, if vv's distance is greater than that of uu's, we can't get to vv because using a teleporter can only decrease our distance to the cycle.

But if this condition isn't satsified, we start at uu and use the teleporters until our distance to the cycle is equal to that of vv's. If we've actually ended up at vv, then our answer is the difference between the distances. Otherwise, it's impossible to reach vv.

To see which planet we end up at if we teleport tt times, we can use binary jumping.

Both in Cycle

If both are in a cycle, we get both uu and vv's index in the cycle. Let's call these indices uiu_i and viv_i respectively. Now, if uiviu_i \leq v_i, then our answer is viuiv_i - u_i. On the other hand, if ui>viu_i > v_i, then our answer is cycle_len(uivi)\texttt{cycle\_len} - (u_i - v_i).

One in Each

This case is really two cases, but we only really need to consider one of them.

If uu is in a cycle but vv is in a tree, it's impossible to reach vv from uu because we can only go from a tree to a cycle, not vice versa.

On the other hand, if uu is the one in the tree, we get which node in the cycle uu's tree connects to, which is also the root. Then this reduces to a version of the second case: we just have to add the distance from uu to the root as well.

Warning!

Note that all three of these cases assume uu and vv are in the same component. If they're in different components, we can't reach vv from uu.

Implementation

Time Complexity: O((n+q)logn)\mathcal{O}((n+q)\log n)

C++

#include <cmath>
#include <iostream>
#include <map>
#include <vector>
using std::cout;
using std::endl;
using std::vector;
int main() {

Java

import java.io.*;
import java.util.StringTokenizer;
public class PlanetQueries2 {
private static int MAX_HEIGHT = 20;
private static int[][] binaryLifting;
private static int[] arr;
private static int[] len;
private static boolean[] visited;

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!