Kattis - Quantum Superposition

Time Complexity: $\mathcal{O}(\sum NM)$

Main Idea: Find all possible lengths of routes in both universes. Then we can preprocess all possible sums of lengths to answer each query in $\mathcal{O}(1)$ time.

Finding All Possible Lengths of Routes

For each node, store all possible lengths of a route that ends at it in a set. We can do this via DP on the topological sort. When we consider a node, we can add 1 to all the lengths reaching a previous node and insert them into the set for the current node. Using a bitset rather than a set is faster (and gives slightly shorter code).

We can repeat this process for both universes to find the total lengths of all paths reaching the end node.

Finding All Possible Sums

Once we know all possible path lengths for each universe, we can find all possible sums of lengths. Just loop through both universe's route lengths and add them together.

Copy
#include <bitset>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

static const int MAX_N = 1000;
static const int MAX_Q = 2000;

int n[2], m[2];

Copy
import java.io.*;
import java.util.*;

public class QuantumSuperposition {
	static final int MAX_N = 1000;
	static final int MAX_Q = 2000;

	static int[] n = new int[2];
	static int[] m = new int[2];
	static ArrayList<Integer>[][] g = new ArrayList[2][MAX_N + 1];

Copy
MAX_N = 1000
MAX_Q = 2000

from collections import deque

n = [0, 0]
m = [0, 0]
g = [[[] for _ in range(MAX_N + 1)] for _ in range(2)]
back = [[[] for _ in range(MAX_N + 1)] for _ in range(2)]
dp = [[[False for _ in range(MAX_Q + 1)] for _ in range(MAX_N + 1)] for _ in range(2)]