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.

1#include <iostream>
2#include <vector>
3#include <queue>
4#include <bitset>
5using namespace std;
6
7int n[2], m[2];
8vector<int> g[2][1001];
9vector<int> back[2][1001];
10bitset<2001> dp[2][1001];