CSES - Game Routes
Authors: Andrew Wang, Sofia Yang
Time Complexity:
This problem is very similar to the "Longest Flight Route" problem discussed earlier in this module. Let denote the number of paths reaching . We can see,
with an exception of , or the starting node, having a value of 1. We process the nodes topologically so will already have been computed before .
C++
#include <iostream>#include <queue>#include <vector>using namespace std;int n;vector<int> edge[100001];vector<int> backedge[100001];int main() {ios_base::sync_with_stdio(0);
Java
import java.io.*;import java.util.*;public class cses1681 {public static final int MOD = (int)1e9 + 7;public static ArrayList<Integer>[] forwards;public static ArrayList<Integer>[] backwards;public static int[] degree;public static int[] dp;
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!