Welcome to my archive . Hope you find it useful.

Tuesday, February 7, 2017

1012 - Guilty Prince - LOJ

#include <bits/stdc++.h>
#define sf scanf
#define pf printf
#define newl '\n'
#define FAST ios_base::sync_with_stdio(0);
#define Case "Case "<<++kase<<": "
#define GRAY 0
#define WHITE 1
#define BLACK 2
using namespace std;

int main()
{
   int T,kase=0;
   cin >> T;
   while(T--){
    int Edgdes;
    cin >> Edgdes;
    vector<int>adj[20000+1];
    int color[20000+1];
    memset(color,GRAY,sizeof color);
    for(int i=0; i<Edgdes; i++){
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    int mx = 0;
    for(int i=0; i<20000+1; i++){
        if((adj[i].size()!=0) && (color[i] == GRAY)){
            int  black=0,white=0;
            queue<int>q;
            q.push(i);
            color[i] = BLACK;
            black++;
            while(!q.empty()){
                int front = q.front();
                q.pop();
                for(int j=0; j<adj[front].size(); j++){
                    if(color[adj[front][j]] == GRAY){
                       
                        if(color[front] == BLACK){
                            color[adj[front][j]] = WHITE;
                            white++;
                        }else if(color[front] == WHITE){
                            color[adj[front][j]] = BLACK;
                            black++;
                        }
                      
                        q.push(adj[front][j]);
                    }
                }
            }
            mx += max(black,white);
        }
    }
    cout <<Case<<mx<<newl;
   }
    return 0;
}

1238 - Power Puff Girls - LOJ

#include <bits/stdc++.h>
#define sf scanf
#define pf printf
#define newl '\n'
#define FAST ios_base::sync_with_stdio(0);
#define Case "Case "<<++kase<<": "
#define GRAY 0
#define WHITE 1
#define BLACK 2
#define imax INT_MAX
#define max3(a,b,c) max(a,max(b,c))
using namespace std;
string grid[21];
int xd[]={-1,0,1,0};
int yd[]={0,1,0,-1};
bool visited[21][21];
int dist[21][21];
int row , col;
int bfs(int i, int j){
    pair<int,int>p;
    queue<pair<int,int> >q;
    int mx = 0;
   for(int i=0; i<21; i++){
        for(int j=0; j<21; j++)dist[i][j]=imax;
    }
    p = {i,j};
    q.push(p);
    dist[i][j] = 0;
    visited[i][j] = true;
    while(!q.empty()){
        pair<int,int>pt;
        pt = q.front();
        q.pop();
        for(int i=0; i<4; i++){
            int x = pt.first;
            int y = pt.second;
            if((x+xd[i]>=0 && x+xd[i]<row) && (y+yd[i]>=0 && y+yd[i]<col) && grid[x+xd[i]][y+yd[i]] == 'h'){
                  dist[x+xd[i]][y+yd[i]] = min(dist[x][y]+1, dist[x+xd[i]][y+yd[i]]);
                  mx = max(mx, dist[x+xd[i]][ y+yd[i]]);
                  return mx;
               
            }else{
                 if((x+xd[i]>=0 && x+xd[i]<row) && (y+yd[i]>=0 && y+yd[i]<col) && (grid[x+xd[i]][y+yd[i]] == '.' ||grid[x+xd[i]][y+yd[i]] == 'a'||grid[x+xd[i]][y+yd[i]] == 'b'||grid[x+xd[i]][y+yd[i]] == 'c' ) && !visited[x+xd[i]][y+yd[i]]){
                    dist[x+xd[i]][ y+yd[i]] = min(dist[x][y]+1, dist[x+xd[i]][y+yd[i]]);
                    mx = max(mx, dist[x+xd[i]][ y+yd[i]]);
                    visited[x+xd[i]][y+yd[i]] = true;
                    q.push({x+xd[i],y+yd[i]});
                }
            }
        }
    }
    return mx;
}
int main()
{
   int T,kase=0;
   cin >> T;
   while(T--){
    cin >> row >> col;
    for(int i=0; i<row; i++){
        cin >> grid[i];
    }
    int a,b,c;
    for(int i=0; i<row; i++){
        for(int j=0; j<col; j++){
            if(grid[i][j] == 'a'){
                memset(visited,0,sizeof visited);
                memset(dist,0,sizeof dist);
                a = bfs(i,j);
            }
            if(grid[i][j] == 'b'){
                memset(visited,0,sizeof visited);
                memset(dist,0,sizeof dist);
                b = bfs(i,j);
            }
            if(grid[i][j] == 'c'){
                memset(visited,0,sizeof visited);
                memset(dist,0,sizeof dist);
                c = bfs(i,j);
            }
        }
    }
        cout<<Case<<max3(a,b,c)<<newl;
   }
    return 0;
}

1009 - Back to Underworld - LOJ

#include <bits/stdc++.h>
#define sf scanf
#define pf printf
#define newl '\n'
#define FAST ios_base::sync_with_stdio(0);
#define Case "Case "<<++kase<<": "
#define GRAY 0
#define WHITE 1
#define BLACK 2
using namespace std;

int main()
{
   int T,kase=0;
   cin >> T;
   while(T--){
    int Edgdes;
    cin >> Edgdes;
    vector<int>adj[20000+1];
    int color[20000+1];
    memset(color,GRAY,sizeof color);
    for(int i=0; i<Edgdes; i++){
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    int mx = 0;
    for(int i=0; i<20000+1; i++){
        if((adj[i].size()!=0) && (color[i] == GRAY)){
            int  black=0,white=0;
            queue<int>q;
            q.push(i);
            color[i] = BLACK;
            black++;
            while(!q.empty()){
                int front = q.front();
                q.pop();
                for(int j=0; j<adj[front].size(); j++){
                    if(color[adj[front][j]] == GRAY){
                        //cout<<front<<' '<<adj[front][j]<<newl;
                        if(color[front] == BLACK){
                            color[adj[front][j]] = WHITE;
                            white++;
                        }else if(color[front] == WHITE){
                            color[adj[front][j]] = BLACK;
                            black++;
                        }
                       // cout<<black<<' '<<white<<newl;
                        q.push(adj[front][j]);
                    }
                }
            }
            mx += max(black,white);
        }
    }
    cout <<Case<<mx<<newl;
   }
    return 0;
}

Tuesday, January 10, 2017

1003 - Drunk - LightOJ

#include <bits/stdc++.h>
#define sf scanf
#define pf printf
#define WHITE 0
#define GRAY 1
#define BLACK 2
#define newl '\n'
#define FAST ios_base::sync_with_stdio(0);
using namespace std;
map<string , int>visited;
map<string, vector<string> >mp;
bool cycle;

void visit(string start){
  visited[start] = GRAY;
  for(int i=0; i<mp[start].size(); i++){
    if(visited[mp[start][i]] == WHITE){
      visit(mp[start][i]);
    }else if(visited[mp[start][i]] == GRAY){
      cycle = true;
      return;
    }
  }
  visited[start] = BLACK;
}

void DFS(){
  map<string, vector<string> >::iterator it;
  visited.clear();
  for(it = mp.begin() ; it!=mp.end(); it++){
    if(cycle)return;
    if(visited[(*it).first] == WHITE){
      visit((*it).first);
    }
  }
}
int main()
{
    FAST;
    int t , kase=0;
    cin >> t;
    while(t--){
      int n;
      cin >> n;
      for(int i=0; i<n; i++){
        string a , b;
        cin >> a >> b;
        mp[a].push_back(b);
        visited[a] = WHITE;
      }
      cycle = false;
      DFS();
      if(cycle)cout<<"Case "<<++kase<<": No"<<newl;
      else cout<<"Case "<<++kase<<": Yes"<<newl;
      mp.clear();
      visited.clear();
    } 

    return 0;
}

Tuesday, December 27, 2016

#include
#define sf scanf
#define pf printf
#define inf 1e18
#define INF 1000000000
#define MAX_N 5001
#define MAX_E 25000001
using namespace std;
typedef long long lld;

int v, e;

int dist[MAX_N];
struct Edge
{
int x, y, weight;
Edge(int _x, int _y, int _weight){
x = _x;
y = _y;
weight = _weight;
}
};
vector E;

int BellmanFord(int source)
{
for (int i=0;i {
if (i == source) dist[i]=0;
else dist[i] = INF;
}
bool done = false;
for (int i=0;!done&&i {
done = true;
for (int j=0;j {
int so = E[j].x;
int de = E[j].y;
if (dist[so] + E[j].weight < dist[de])
{
dist[de] = dist[so] + E[j].weight;
done=false;
}
}
}
if (!done) return -1;
return 0;
}

int main()
{
int t;
cin >> t;
while(t--){
E.clear();
v , e;
cin >> v >> e;
for(int i=0; i int u , v , w;
cin >> u >> v >> w;
E.push_back(Edge(u,v,w));
}
BellmanFord(0) == -1 ? cout<<"possible\n":cout<<"not possible\n";
}

return 0;

}

UVA 10986 - Sending email

#include <bits/stdc++.h>
#define sf scanf
#define pf printf
#define inf 1e18
#define MAX 1000000000
using namespace std;
struct Node{
int at , cost;
Node(int _at, int _cost){
at = _at;
cost = _cost;
}
};
bool operator<(Node A , Node B){
return A.cost > B.cost;
}
struct Edge{
int v, w;
Edge(int _v, int _w){
v = _v;
w = _w;
}
};
vector <Edge> adj[20000+1];
priority_queue<Node>PQ;
int dist[20000+1];
int n;

void dijkstra(int s){
for(int i=0; i<=n; i++){
dist[i] = MAX;
}
dist[s] = 0;
PQ.push(Node(s,0));

while(!PQ.empty()){
Node u = PQ.top();
PQ.pop();
if(u.cost != dist[u.at]){
continue;
}
for(Edge e: adj[u.at]){
if(dist[e.v] > u.cost + e.w){
dist[e.v] = u.cost + e.w;
PQ.push(Node(e.v, dist[e.v]));
}
}
}
}
int main()
{
ios_base::sync_with_stdio(0);
int t,kase=0;
cin >> t;
while(t--){
memset(adj,0,sizeof adj);
while(!PQ.empty())PQ.pop();
int edges , s , t;
cin >> n >> edges >> s >>t;
for(int i=0; i<edges; i++){
int u , v , w;
cin >>u >> v >> w;
adj[u].push_back(Edge(v,w));
adj[v].push_back(Edge(u,w));
}
dijkstra(s);
if(dist[t] == MAX)cout <<"Case #"<<++kase<<": unreachable\n";
else cout <<"Case #"<<++kase<<": "<<dist[t]<<'\n';
}

return 0;
}

Sunday, December 25, 2016

UVA 762 - We Ship Cheap

#include <bits/stdc++.h>
#define sf scanf
#define pf printf
using namespace std;
map<string, bool>visited;
void bfs(string start , string end , map<string , vector<string> >mp)
{
vector<pair<string, string> >vp;
queue<string>q;
q.push(start);
visited[start] = true;
bool flag = false;
while(!q.empty()){
string top = q.front();
q.pop();
for(int i=0; i<mp[top].size(); i++){
if(!visited[mp[top][i]]){
visited[mp[top][i]] = true;
if(mp[top][i] != end){
vp.push_back(make_pair(top , mp[top][i]));
q.push(mp[top][i]);
}else if(mp[top][i] == end){
flag = true;
vp.push_back(make_pair(top , mp[top][i]));
break;
}
}
}
if(flag)break;
}
if(!flag && q.empty())cout << "No route\n";
else{
for(int i=0; i<vp.size(); i++)
cout << vp[i].first<< ' '<<vp[i].second<<'\n';
}

}
int main()
{
ios_base::sync_with_stdio(0);
int t;
bool first = true;
while(cin >> t){
if(!first)cout <<'\n';
first = false;
map<string , vector<string> > mp;
visited.clear();
while(t--){
string u , v;
cin >> u >> v;
mp[u].push_back(v);
mp[v].push_back(u);
}
string start, end;
cin >> start >> end;
bfs(start , end , mp);
}
}