LightOJ - 1004 - Monkey Banana Problem

1. /****************#####    بِسْمِ اللَّهِ الرَّحْمَنِ الرَّحِيم   #####******************
2. __________________________________________________________________________
3. ######################  Ya-Seen Arafat(ACWizard) #########################
4. ######################        UAP-CSE-33B        #########################
5. *************************************************************************/
6. #include <bits/stdc++.h>
7. #define sc(n) scanf("%d", &n)
8. #define scD(n) scanf("%lf", &n)
9. #define scS(n) scanf("%s", &n)
10. #define S 103
11. using namespace std;
13. int n, ar[S*3][S];
14. int dp[S*3][S], sz[S*3];
16. int MB(int row, int ind, int jump){
17.     if(row > (n+n-1) || ind < 0 || ind > sz[jump])return 0;
18.     if(dp[jump][ind] != -1)return dp[jump][ind];
19.     if(row < n)dp[jump][ind] = (ar[jump][ind] + max(MB(row+1, ind, jump+1), MB(row+1, ind+1, jump+1)));
20.     else dp[jump][ind] = (ar[jump][ind] + max(MB(row+1, ind-1, jump+1), MB(row+1, ind, jump+1)));
21.     return dp[jump][ind];
22. }
24. int main(){
25.     int t, cs = 0;
26.     scanf("%d", &t);
27.     while(t--){
28.         memset(dp, -1, sizeof(dp));
29.         memset(ar, 0, sizeof(ar));
30.         scanf("%d", &n);
31.         int z;
32.         for(int i = 0; i < n; i++){
33.             for(int j = 0; j <= i; j++){
34.                 scanf("%d", &ar[i][j]);
35.             }
36.             sz[i] = i;
37.             z = i;
38.         }
39.         int jj = n-1;
40.         for(int i = z+1; i < (n+n-1); i++){
41.             for(int j = 0; j < jj; j++){
42.                 scanf("%d", &ar[i][j]);
43.             }
44.             sz[i] = jj-1;
45.             jj--;
46.         }
47.         int ans = MB(1, 0, 0);
48.         cout << "Case " << ++cs << ": " << ans << endl;
49.     }
50.     return 0;
51. }

LightOJ - 1009 - Back to Underworld --- using BFS

1. /****************#####    بِسْمِ اللَّهِ الرَّحْمَنِ الرَّحِيم   #####******************
2. __________________________________________________________________________
3. ######################  Ya-Seen Arafat(ACWizard) #########################
4. ######################        UAP-CSE-33B        #########################
5. *************************************************************************/
6. #include <bits/stdc++.h>
7. #define sc(n) scanf("%d", &n)
8. #define scD(n) scanf("%lf", &n)
9. #define scS(n) scanf("%s", &n)
10. #define S 20003
11. #define SS 100003
12. using namespace std;
13. typedef long long LL;
14.  
15. vector <int> race[S], edge;
16. int ans[S], check[S];
17.  
18. int BFS(int src){
19.     int anss = 0;
20.     queue <int> Q;
21.     Q.push(src);
22.     int sz = edge.size();
23.     ans[src] = 1;
24.     while(!Q.empty()){
25.         int x, y;
26.         x = Q.front();
27.         check[x]++;
28.         Q.pop();
29.         y = race[x].size();
30.         for(int i = 0; i < y; i++){
31.             if(!ans[race[x][i]]){
32.                 Q.push(race[x][i]);
33.                 if(ans[x] == 1)ans[race[x][i]] = 2;
34.                 if(ans[x] == 2)ans[race[x][i]] = 1;
35.             }
36.         }
37.         if(Q.empty()){
38.             int vamp = 0, lyk = 0;
39.             for(int i = 0; i < S; i++){
40.                     if(ans[i] == 1)vamp++;
41.                     if(ans[i] == 2)lyk++;
42.                     ans[i] = 0;
43.             }
44.             anss += max(vamp, lyk);
45.             for(int i = 0; i < sz; i++){
46.                 if(check[edge[i]] == 1){
47.                     Q.push(edge[i]);
48.                     ans[edge[i]] = 1;
49.                     break;
50.                 }
51.             }
52.         }
53.     }
54.     return anss;
55. }
56.  
57. void Do(){
58.     int t, n, u, v, cs = 0;
59.     sc(t);
60.     while(t--){
61.         sc(n);
62.         memset(ans, 0, sizeof(ans));
63.         memset(check, 0, sizeof(check));
64.         for(int i = 0; i < S; i++)race[i].clear();
65.         edge.clear();
66.         while(n--){
67.             sc(u);
68.             sc(v);
69.             if(!check[u])check[u] = 1, edge.push_back(u);
70.             if(!check[v])check[v] = 1, edge.push_back(v);
71.             race[u].push_back(v);
72.             race[v].push_back(u);
73.         }
74.         int members = BFS(u);
75.         printf("Case %d: %d\n", ++cs, members);
76.     }
77. }
78.  
79. int main(){
80.     ios_base::sync_with_stdio(0); cin.tie(0);
81.     #ifndef ONLINE_JUDGE
82.     ///freopen("contest.txt","w",stdout);
83.     #endif
84.     Do();
85.     return 0;
86. }