P_Sarker Coding House

/*     Accepted     Algorithm: Dijkstra     The sample of this problem is also solvable using BFS algorithm, but to find     minimum the problem is an optimization problem. So, the Dijkstra algorithm is     perfect for it. This is straight forward Dijkstra. But, you should visit     each position (x, y) as one time to avoid TLE. */ #include<bits/stdc++.h> using namespace std; #define sf scanf #define pf printf #define psb push_back #define fast ios_base::sync_with_stdio(false) typedef map<string, int>mpsi; typedef map<int, string>mpis; typedef long long LL; const int high = 1005; const int inf = (1 << 31) - 1; vector<LL>adj[high]; vector<LL>nodelist; int matrix[high][high], visited[high][high], cost[high][high]; int N , M , test; int move_x[] = {1, -1, 0, 0}; int move_y[] = {0, 0, 1, -1}; struct data {     int node1, node2, cost;     data() { }     data(int n1 , int n2, int c)     {         node1 = n1;         node2 = n2;         cost = c;     }    

/*     Accepted     Algorithm: BFS with printing the path */ #include<bits/stdc++.h> using namespace std; #define sf scanf #define pf printf #define psb push_back #define fast ios_base::sync_with_stdio(false) typedef map<string, int>mpsi; typedef map<int, string>mpis; const int high = 1e5+10; int visited[high] , par[high]; vector<int>adj[high]; mpsi mp1; mpis mp2; void CLRv1() {     for(int i=0; i<high; i++)     {         adj[i].clear();     }     mp1.clear();     mp2.clear(); } void CLRv2() {     for(int i=0; i<high; i++)     {         visited[i] = 0;         par[i] = 0;     } } void BFS(int s, int d) {     visited[s] = 1;     queue<int>Q;     Q.push(s);     while(!Q.empty())     {         int u = Q.front();         Q.pop();         if(u == d) return;         int sze = adj[u].size();         for(int i=0; i<sze; i++)         {             int v = adj[u][i];             if(!visited[v])             {                 par[v] = u;                 visi

Problem Link: https://uva.onlinejudge.org/external/5/573.pdf *********************** Solution *********************** #include<bits/stdc++.h> using namespace std; #define sf scanf #define pf printf #define psb push_back #define fast ios_base::sync_with_stdio(false) typedef map<string, int>mpsi; typedef map<int, string>mpis; typedef long long LL; const int high = 2e5+10; int main() {     fast;     double H, U, D, F;     while(cin >> H && H)     {         cin >> U >> D >> F;         bool fail = false;         int day = 0;         F = (F * U) * 0.01;         //cout << "F = " << F << "\n";         double cnt = 0.0;         double tmp = U;         while(true)         {             day += 1;             cnt = tmp > 0.0 ? cnt + tmp : cnt;             //cout << "1. cnt = " << cnt << " day = " << day << "\n";             if(cnt > H)    

/*     Accepted     Just match the test cases :D :D */ #include<bits/stdc++.h> using namespace std; #define sf scanf #define pf printf #define psb push_back #define fast ios_base::sync_with_stdio(false) typedef map<string, int>mpsi; typedef map<int, string>mpis; typedef long long LL; const int high = 2e5+10; void Solution(int N , int M , int x , int y) {     if(x == N || y == M)     {         cout << "divisa\n";     }     else if(x > N && y > M)     {         cout << "NE\n";     }     else if(x > N && y < M)     {         cout << "SE\n";     }     else if(x < N && y > M)     {         cout << "NO\n";     }     else if(x < N && y < M)     {         cout << "SO\n";     } } int main() {     fast;     int K;     while(cin >> K && K)     {         int N , M ;         cin >> N >> M;         while(K--)         {   

/*     Accepted */ #include<bits/stdc++.h> using namespace std; #define sf scanf #define pf printf #define psb push_back #define fast ios_base::sync_with_stdio(false) typedef map<string, int>mpsi; typedef map<int, string>mpis; typedef long long LL; const int high = 2e5+10; char checkReverse(char ch) {     if(ch == 'A') return 'A';     else if(ch == 'A') return 'A';     else if(ch == 'E') return '3';     else if(ch == '3') return 'E';     else if(ch == 'H') return 'H';     else if(ch == 'I') return 'I';     else if(ch == 'J') return 'L';     else if(ch == 'L') return 'J';     else if(ch == 'M') return 'M';     else if(ch == 'O') return 'O';     else if(ch == 'S') return '2';     else if(ch == '2') return 'S';     else if(ch == 'T') return 'T';     else if(ch == &#

/*     Accepted     Algorithm: BFS     Solution: (Total cost to reach the destination) - 1 */ #include<bits/stdc++.h> using namespace std; #define sf scanf #define pf printf #define psb push_back #define fast ios_base::sync_with_stdio(false) typedef map<string, int>mpsi; typedef map<int, string>mpis; typedef long long LL; const int high = 2e5+10; vector<int>adj[high]; int visited[high], cost[high]; void CLR() {     for(int i=0; i<high; i++)     {         adj[i].clear();         cost[i] = 0;         visited[i] = 0;     } } void BFS(int s , int d) {     visited[s] = 1;     cost[s] = 0;     queue<int>Q;     Q.push(s);     while(!Q.empty())     {         int u = Q.front();         Q.pop();         if(u == d) return;         int sze = adj[u].size();         for(int i=0; i<sze; i++)         {             int v = adj[u][i];             if(!visited[v])             {                 visited[v] = 1;                 Q.push(v);                 cost[v] = cost[u]

/*     RTE  |             - got two RTE due to the recursion function (path()), so be careful of it.     RTE  |     WA     Finally, Accepted     Nice Problem for beginning.     Algorithm: BFS     with printing the Path */ #include<bits/stdc++.h> using namespace std; #define sf scanf #define pf printf #define psb push_back #define fast ios_base::sync_with_stdio(false) typedef map<string, int>mpsi; typedef map<int, string>mpis; typedef long long LL; const int high = 11115; mpsi mp; mpis rmp; vector<LL>adj[high]; vector<LL>nodelist; LL visited[high], par[high]; bool isPath = true; void CLR() {     for(int i=0; i<high; i++)     {         adj[i].clear();         visited[i] = 0;         par[i] = 0;     }     mp.clear();     rmp.clear();     nodelist.clear();     isPath = true; } void BFS(int s) {     visited[s] = 1;     queue<LL>Q;     Q.push(s);     //par[s] = s;     while(!Q.empty())     {         LL u = Q.front();         Q.pop();         LL sze = a

#include<bits/stdc++.h> using namespace std; #define sf scanf #define pf printf #define psb push_back #define fast ios_base::sync_with_stdio(false) const int high = 105; const int red = 1; const int blue = 0; const int white = -1; bool bipartite = true; typedef map<string, int>mpsi; vector<int>adj[high]; int cost[high], visited[high]; mpsi mp; void CLR() {     for(int i=0; i<high; i++)     {         adj[i].clear();     }     mp.clear(); } void CLR_cost() {     for(int i=0; i<high; i++)     {         cost[i] = 0;         visited[i] = 0;     } } void BFS(int src, int des) {     visited[src] = 1;     cost[src] = 0;     queue<int>Q;     Q.push(src);     while(!Q.empty())     {         int u = Q.front();         Q.pop();         if(u == des) return;         int sze = adj[u].size();         for(int i=0; i<sze; i++)         {             int v = adj[u][i];             if(!visited[v])             {                 visited[v] = 1;                 Q.push(v);    

// Accepted #include<bits/stdc++.h> using namespace std; #define sf scanf #define pf printf #define psb push_back #define fast ios_base::sync_with_stdio(false) const int high = 2010; int visited[high] , dis[high]; vector<int>adj[high]; void CLR() {     for(int i=0; i<high; i++)     {         visited[i] = 0;         dis[i] = 0;         adj[i].clear();     } } void BFS(int s) {     visited[s] = 1;     dis[s] = 0;     queue<int>Q;     Q.push(s);     while(!Q.empty())     {         int u = Q.front();         Q.pop();         int sze = adj[u].size();         for(int i=0; i<sze; i++)         {             int v = adj[u][i];             if(!visited[v])             {                 dis[v] = dis[u] + 1;                 visited[v] = 1;                 Q.push(v);             }         }     } } int main() {     fast;     int i, test;     cin >> test;     while(test--)     {         CLR();         int P, D;         cin >> P >> D;         for(i=0; i<D;

/*     Accepted     Algorithm: BFS     Check whether the given graph is Bipartite or not. If not then put -1 otherwise find     the minimum number of guards. Note that, single connected component is needed minimum one guard. */ #include<bits/stdc++.h> using namespace std; #define sf scanf #define pf printf #define psb push_back #define fast ios_base::sync_with_stdio(false) const int high = 505; const int red = 1; const int blue = 0; const int white = -1; bool bipartite = true; vector<int>adj[high]; int guards = 0 , color[high] , count_red = 0 , count_blue = 0; void CLR() {     for(int i=0; i<high; i++)     {         adj[i].clear();         color[i] = white;     }     bipartite = true;     count_blue = 0;     count_red = 0;     guards = 0; } void BFS(int s) {     color[s] = red;     queue<int>Q;     Q.push(s);     count_red+=1;     while(!Q.empty() && bipartite)     {         int u = Q.front();         Q.pop();         int sze = adj[u].size();         for(i

/* Accepted */ /*     Algorithm: BFS     Just take the maximum adjacent nodes and calculate the units of it as well as keep     track about the last node where you are terminating your graph traverse. */ #include<bits/stdc++.h> using namespace std; #define sf scanf #define pf printf #define psb push_back #define fast ios_base::sync_with_stdio(false) const int high = 205; int units[high], visited[high], total = 0; int mxx = -1 , mxxnode = 0, lastnode = 0; vector<int>adj[high]; void CLR() {     for(int i=0; i<high; i++)     {         adj[i].clear();         units[i] = 0;         visited[i] = 0;     }     total = 0; } void BFS(int s) {     visited[s] = 1;     queue<int>Q;     Q.push(s);     while(!Q.empty())     {         int u = Q.front();         lastnode = u;         total += units[u];         Q.pop();         int sze = adj[u].size(), v;         mxx = -1 , mxxnode = 0;         for(int i=0; i<sze; i++)         {             v = adj[u][i];             if(mxx <

/**   *  @Author: Pranta Sarker   *   **/ #include<bits/stdc++.h> using namespace std; #define sf scanf #define pf printf int move_x[8] = {2, 1, -1, -2, -2, -1,  1,  2}; int move_y[8] = {1, 2,  2,  1, -1, -2, -2, -1}; int visited[10][10], s_row=0, s_col=0, d_row=0, d_col=0; int cost[10][10]; void BFS(int r, int c) {     visited[r][c] = 1;     cost[r][c] = 0;     queue<int>Q;     Q.push(r);     Q.push(c);     while(!Q.empty())     {         int ux = Q.front();         Q.pop();         int uy = Q.front();         Q.pop();         for(int i=0; i<8; i++)         {             int vx = ux + move_x[i];             int vy = uy + move_y[i];             if((vx > 0 && vx <= 8) && (vy >0 && vy <= 8) && !visited[vx][vy])             {                 cost[vx][vy] = cost[ux][uy] + 1;                 visited[vx][vy] = 1;                 Q.push(vx);                 Q.push(vy);             }         }     } } void CLR() {     for(int i=0; i&l

/**   *  @Author: Pranta Sarker   *   @Status: Accepted   *   **/ #include<bits/stdc++.h> using namespace std; #define sf scanf #define pf printf #define psb push_back const int white = 0; const int grey = 1; const int black = -1; const int high = (2e5)+10; vector<int>adj[high]; int status[high]; vector<int>sortedList; void CLR() {     for(int i=0; i<high; i++)     {         adj[i].clear();     }     sortedList.clear(); } void CLR_status() {     for(int i=0; i<high; i++)     {         status[i] = white;     } } void Topo_Sort(int u, int pmeter) {     status[u] = grey;     int sze = adj[u].size();     for(int i=0; i<sze; i++)     {         int v = adj[u][i];         if(status[v] == white)         {             Topo_Sort(v, pmeter);         }     }     if(pmeter == 0)     {         sortedList.push_back(u);     }     status[u] = black; } int main() {     int test , n , m, i , u , v;     sf("%d", &test);     while(test--)     {         CLR();      

/**************************** *                           * *   @Author: Pranta Sarker  * *    @Status: Accepted       * *                           * ****************************/ #include<bits/stdc++.h> using namespace std; #define sf scanf #define pf printf #define psb push_back const int high=205; const int white=0; const int grey=1; const int black=-1; vector<int>adj[high]; int status[high]; vector<int>sortedList; void CLR() {     int i=0;     for(i=0; i<high; i++)     {         status[i]=white;         adj[i].clear();     }     sortedList.clear(); } void Topo_Sort(int u) {     status[u] = grey;     int i, sze = adj[u].size();     for(i=0; i<sze; i++)     {         int v = adj[u][i];         if(status[v] == white)         {             Topo_Sort(v);         }     }     status[u] = black;     sortedList.push_back(u); } int main() {     int u, v, i, n, m;     while(sf("%d %d", &n, &m)==2)     {         if(!m && !n) break;         CL