[toph.co] Keep Moving

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : Keep Moving
Source            : toph.co
Category          : Game Theory
Algorithm         : Decision Tree
Verdict           : Accepted

1. #include "bits/stdc++.h"  
2.   
3. using namespace std;  
4.   
5. #define sz(a)             (int)a.size()  
6. #define eb                emplace_back  
7.   
8. static const int maxn = 1e5 + 5;  
9.   
10. int tnode, tedge, x;  
11. vector <int> graph[maxn];  
12.   
13. int dp[maxn];  
14. bool memoize[maxn];  
15.   
16. inline bool dicisionTree(int cur)  
17. {  
18.     if (sz(graph[cur]) == 0) return false; // lossing state  
19.     int &ret = dp[cur];  
20.     bool &mem = memoize[cur];  
21.     if (mem) return ret;  
22.     mem = 1;  
23.     for (int nxt : graph[cur])  
24.     {  
25.         if (dicisionTree(nxt) == false)   
26.         {  
27.             return ret = true;  
28.         }  
29.     }  
30.     return ret = false;  
31. }  
32.   
33. int main()  
34. {  
35.     int tc;  
36.     cin >> tc;  
37.     for (int tcase = 1; tcase <= tc; tcase++)  
38.     {  
39.         cin >> tnode >> tedge >> x;  
40.         for (int i = 0; i < tedge; i++)  
41.         {  
42.             int u, v;  
43.             cin >> u >> v;  
44.             graph[u].eb(v); // DAG  
45.         }  
46.         memset(memoize, 0, sizeof memoize);  
47.         if (dicisionTree(x)) cout << "Case " << tcase << ": Yes\n";  
48.         else cout << "Case " << tcase << ": No\n";  
49.         for (int i = 0; i < maxn; i++) graph[i].clear();  
50.     }  
51. }