1238 - Power Puff Girls

Problem Link : http://lightoj.com/volume_showproblem.php?problem=1238

Solution :

#include<bits/stdc++.h>
#define pii pair<int,int>

using namespace std;

int cell[22][22];
int visited[22][22];
int dis[22][22];

int fx[]= {1,-1,0,0};
int fy[]= {0,0,1,-1};

int r,c;

int bfs(pii s,pii d)
{
    memset(visited,0,sizeof(visited));

    memset(dis,0,sizeof(dis));

    visited[s.first][s.second]=1;
    dis[s.first][s.second]=0;

    queue<pii>q;
    pii u,a;
    int x,y,cnt=0;
    q.push(s);

    while(!q.empty())
    {
        u=q.front();
        q.pop();

        for(int i=0; i<4; i++)
        {
            x=fx[i]+u.first;
            y=fy[i]+u.second;

            if(x>=0 and x<r and y>=0 and y<c and cell[x][y]!=2 and visited[x][y]==0)
            {
                visited[x][y]=1;
                dis[x][y]=dis[u.first][u.second]+1;
                cnt++;
                a.first=x;
                a.second=y;
                q.push(a);
            }
        }

    }
    return dis[d.first][d.second];

}

int main()
{
    int t,ans;
    char ch;
    pii s,s1,s2,d;
    scanf("%d",&t);


    for(int ca=1; ca<=t; ca++)
    {
        scanf("%d%d",&r,&c);
        getchar();
        memset(cell,-1,sizeof(cell));
        for(int i=0; i<r; i++)
        {
            for(int j=0; j<c; j++)
            {
                scanf("%c",&ch);
                if(ch=='.') cell[i][j]=1;
                else if(ch=='#') cell[i][j]=2;
                else if(ch=='c')
                {
                    cell[i][j]=3;
                    s1.first=i;
                    s1.second=j;
                }
                else if(ch=='a')
                {
                    cell[i][j]=4;
                    s2.first=i;
                    s2.second=j;
                }
                else if(ch=='b')
                {

                    cell[i][j]=5;
                    s.first=i;
                    s.second=j;
                }
                else if(ch=='h')
                {
                    cell[i][j]=6;
                    d.first=i;
                    d.second=j;
                }
                else
                {
                    cell[i][j]=2;
                }

            }
            getchar();
        }

        ans=bfs(s,d);
        ans=max(ans,bfs(s1,d));
        ans=max(ans,bfs(s2,d));

        printf("Case %d: %d\n",ca,ans);
    }

}

1257 - Farthest Nodes in a Tree (II)

Problem Link : http://lightoj.com/volume_showproblem.php?problem=1257

Solution :


#include<bits/stdc++.h>
#define inf 1e9
#define ll long long

using namespace std;

vector<ll int> v[30005],cost[30005];

ll int dis[30005];
ll int dis1[30005];
ll int n;



struct node
{
    ll int city,dist;

    node(ll int a,ll int b)
    {
        city=a;
        dist=b;
    }

    bool operator <(const node &p)const
    {
        return p.dist<dist;
    }
};

void func(ll int s)
{

    for(ll int i=0; i<30005; i++) dis1[i]=inf;

    ll int mx=-1,p;

    dis1[s]=0;
    priority_queue<node>q;

    q.push(node(s,0));

    while(!q.empty())
    {

        node t=q.top();
        q.pop();

        ll int u=t.city;

        for(ll int i=0; i<v[u].size(); i++)
        {
            ll int p=v[u][i];

            if(dis1[p]>(dis1[u]+cost[u][i]))
            {
                dis1[p]=(dis1[u]+cost[u][i]);
                q.push(node(p,dis1[p]));

            }
        }
    }



}
ll int dijkstra(ll int s)
{

    for(ll int i=0; i<30005; i++) dis[i]=inf;

    ll int mx=-1,p;

    dis[s]=0;
    priority_queue<node>q;

    q.push(node(s,0));

    while(!q.empty())
    {

        node t=q.top();
        q.pop();

        ll int u=t.city;

        for(ll int i=0; i<v[u].size(); i++)
        {
            ll int p=v[u][i];

            if(dis[p]>(dis[u]+cost[u][i]))
            {
                dis[p]=(dis[u]+cost[u][i]);
                q.push(node(p,dis[p]));

            }
        }
    }
    for(ll int i=0; i<n; i++)
    {
        if(dis[i]>mx)
        {
            mx=dis[i];
            p=i;
        }
    }


    return p;


}
int main()
{


    ll int t,a,b,c,ans=0,s=0,mx;

    scanf("%lld",&t);

    for(ll int ca=1; ca<=t; ca++)
    {
        scanf("%lld",&n);
        s=0,mx=-1,ans=0;


        for(ll int i=0; i<n-1; i++)
        {

            scanf("%lld%lld%lld",&a,&b,&c);



            v[a].push_back(b);
            v[b].push_back(a);
            cost[a].push_back(c);
            cost[b].push_back(c);

        }


        ans=dijkstra(1);
        ans=dijkstra(ans);
        func(ans);

        printf("Case %lld:\n",ca);

       for(int i=0;i<n;i++)
       {
           printf("%lld\n",max(dis[i],dis1[i]));
       }


        for(ll int i=0; i<30005; i++)
        {
            v[i].clear();
            cost[i].clear();
        }

    }

}

1094 - Farthest Nodes in a Tree

Problem Link : http://lightoj.com/volume_showproblem.php?problem=1094

Solution :


#include<bits/stdc++.h>
#define inf 1e9
#define ll long long

using namespace std;

vector<ll int> v[30005],cost[30005];

ll int dis[30005];
ll int n;



struct node
{
    ll int city,dist;

    node(ll int a,ll int b)
    {
        city=a;
        dist=b;
    }

    bool operator <(const node &p)const
    {
        return p.dist<dist;
    }
};

ll int dijkstra(ll int s)
{

    for(ll int i=0; i<30005; i++) dis[i]=inf;

    ll int mx=-1,p;

    dis[s]=0;
    priority_queue<node>q;

    q.push(node(s,0));

    while(!q.empty())
    {

        node t=q.top();
        q.pop();

        ll int u=t.city;

        for(ll int i=0; i<v[u].size(); i++)
        {
            ll int p=v[u][i];

            if(dis[p]>(dis[u]+cost[u][i]))
            {
                dis[p]=(dis[u]+cost[u][i]);
                q.push(node(p,dis[p]));

            }
        }
    }
    for(ll int i=0; i<n; i++)
    {
        if(dis[i]>mx)
        {
            mx=dis[i];
            p=i;
        }
    }


    return p;


}
int main()
{


    ll int t,a,b,c,ans=0,s=0,mx;

    scanf("%lld",&t);

    for(ll int ca=1; ca<=t; ca++)
    {
        scanf("%lld",&n);
        s=0,mx=-1,ans=0;


        for(ll int i=0; i<n-1; i++)
        {

            scanf("%lld%lld%lld",&a,&b,&c);



            v[a].push_back(b);
            v[b].push_back(a);
            cost[a].push_back(c);
            cost[b].push_back(c);

        }


        ans=dijkstra(1);
        ans=dijkstra(ans);
        ans=dis[ans];



        printf("Case %lld: %lld\n",ca,ans);


        for(ll int i=0; i<30005; i++)
        {
            v[i].clear();
            cost[i].clear();
        }

    }
}

1012 - Guilty Prince

Problem Link : http://lightoj.com/volume_showproblem.php?problem=1012

Solution :

#include<bits/stdc++.h>
#define pii pair<int,int>

using namespace std;

int cell[21][21];
int visited[21][21];

int fx[]= {1,-1,0,0};
int fy[]={0,0,1,-1};

int r,c;

int bfs(pii s)
{
    memset(visited,0,sizeof(visited));

    visited[s.first][s.second]=1;

    queue<pii>q;
    pii u,a;
    int x,y,cnt=0;
    q.push(s);

    while(!q.empty())
    {
        u=q.front();
        q.pop();

        for(int i=0;i<4;i++)
        {
            x=fx[i]+u.first;
            y=fy[i]+u.second;

            if(x>=0 and x<r and y>=0 and y<c and cell[x][y]!=2 and visited[x][y]==0)
            {
                visited[x][y]=1;
                cnt++;
                a.first=x;
                a.second=y;
                q.push(a);
            }
        }

    }
    return cnt+1;
}

int main()
{
    int t,ans;
    char ch;
    pii s;
    scanf("%d",&t);


    for(int ca=1; ca<=t; ca++)
    {
        scanf("%d%d",&c,&r);
        getchar();
        memset(cell,-1,sizeof(cell));
        for(int i=0; i<r; i++)
        {
            for(int j=0; j<c; j++)
            {
                scanf("%c",&ch);
                if(ch=='.') cell[i][j]=1;
                else if(ch=='#') cell[i][j]=2;
                else
                {
                    cell[i][j]=3;
                    s.first=i;
                    s.second=j;
                }

            }
            getchar();
        }

        ans=bfs(s);

        printf("Case %d: %d\n",ca,ans);
    }
}

1009 - Back to Underworld

Problem Link: http://www.lightoj.com/volume_showproblem.php?problem=1009

Solution :

#include<bits/stdc++.h>

using namespace std;

vector<int>v[200001];
vector<int>node;

int visited[200001],cnt,mnt;

map<int,string>mp;
map<int,string> :: iterator it;

void bfs(int source)
{

    cnt=0,mnt=0;

    queue<int>q;

    q.push(source);

    visited[source]=0;
    cnt++;

    int u,p;

    while(!q.empty())
    {
        u=q.front();

        if(mp[u]=="black" and visited[u]==-1) cnt++;
        else if(mp[u]=="red" and visited[u]==-1) mnt++;

        q.pop();
        for(int i=0; i<v[u].size(); i++)
        {
            p=v[u][i];

            if(visited[p]==-1)
            {
                if(mp[u]=="black") mp[p]="red",mnt++;
                else mp[p]="black",cnt++;

                visited[p]=visited[u]+1;
                q.push(p);
            }

        }
    }
}

int main()
{

    int t,e,a,b,ans;
    scanf("%d",&t);

    for(int ca=1; ca<=t; ca++)
    {
        scanf("%d",&e);

        cnt=0,mnt=0,ans=0;

        for(int i=1; i<=e; i++)
        {


            scanf("%d%d",&a,&b);

            v[a].push_back(b);
            v[b].push_back(a);

            node.push_back(a);
            node.push_back(b);

            mp[a]="black";
            mp[b]="black";
        }
        memset(visited,-1,sizeof(visited));

        for(int i=0; i<node.size(); i++)
        {
            if(visited[node[i]]==-1)
            {
                bfs(node[i]);
                ans=ans+max(cnt,mnt);
            }
        }

        printf("Case %d: %d\n",ca,ans);

        for(int i=0; i<200001; i++) v[i].clear();

        mp.clear();
        node.clear();

    }

}

1174 - Commandos

Problem Link : http://lightoj.com/volume_showproblem.php?problem=1174

Solution:

#include<bits/stdc++.h>
#define inf 1000000

using namespace std;


int dis [101][101];


int main()
{


    int n,e,t;
    int a,b,c;
    int s,d,w;

    scanf("%d",&t);

    for(int ca=1; ca<=t; ca++)
    {

        scanf("%d%d",&n,&e);

        for(int i=0; i<n; i++)
        {
            for(int j=0; j<n; j++)
            {
                if (i==j)
                {
                    dis[i][j]=0;
                }
                else
                {
                    dis[i][j]=inf;
                }
            }
        }





        for(int i=0; i<e; i++)
        {
            scanf("%d%d",&a,&b);

            dis[a][b]=1;
            dis[b][a]=1;


        }

        for(int k=0; k<n; k++)

            for(int i=0; i<n; i++)

                for(int j=0; j<n; j++)
                {
                    if(dis[i][j]>dis[i][k]+dis[k][j])
                    {
                        dis[i][j]=dis[i][k]+dis[k][j];

                    }
                }


        w=1;
        if(e==0) w=0;
        scanf("%d%d",&s,&d);

        for(int i=0; i<n; i++)
        {
            if(s!=i and d!=i) w=max(w,dis[s][i]+dis[i][d]);
        }



        printf("Case %d: %d\n",ca,w);
    }
}

1002 - Country Roads

Problem Link : http://lightoj.com/volume_showproblem.php?problem=1002

Solution :

#include<bits/stdc++.h>
#define inf 100000

using namespace std;

vector<int> v[600],cost[600];

int dis[600];


struct node
{
    int city,dist;

    node(int a,int b)
    {
        city=a;
        dist=b;
    }

    bool operator <(const node &p)const
    {
        return p.dist<dist;
    }
};

void dijkstra(int s)
{

    for(int i=0;i<600;i++) dis[i]=inf;

    dis[s]=0;

    priority_queue<node>q;

    q.push(node(s,0));

    while(!q.empty())
    {

       node t=q.top();
        q.pop();

        int u=t.city;

        for(int i=0;i<v[u].size();i++)
        {
            int p=v[u][i];

            if(dis[p]>max(dis[u],cost[u][i]))
            {
                dis[p]=min(dis[p],max(dis[u],cost[u][i]));
                q.push(node(p,dis[p]));

            }
        }
    }

}

int main()
{



    int n,e,t,a,b,c,s;
    scanf("%d",&t);

for(int ca=1;ca<=t;ca++)

  {

scanf("%d%d",&n,&e);


    for(int i=1;i<=e;i++)
    {
        scanf("%d%d%d",&a,&b,&c);

        v[a].push_back(b);
        v[b].push_back(a);
        cost[a].push_back(c);
        cost[b].push_back(c);
    }

    scanf("%d",&s);



    dijkstra(s);

    printf("Case %d:\n",ca);

    for(int i=0;i<n;i++)
    {
        if(dis[i]==inf) printf("Impossible\n");
        else printf("%d\n",dis[i]);
    }

    for(int i=0;i<600;i++)
    {
        v[i].clear();
        cost[i].clear();
    }

  }

}