Light oj 1059 solution

MST & BFS Combine
লাইট অজ ১০৫৯
এমনিতে মিনিমাম ডিসট্যান্স বের করে +কত গুলোর জন্য বি এফ এস আলাদা ভাবে চালান লাগছে সেইগুলোর সাথে   এইচ বার বার গুন
2
4 4 100
1 2 10
4 3 12
4 1 41
2 3 23

উত্তর আসছে ১০+১২+২৩+(১০০*১)=১৪৫
আউটপুট ঃ Case 1: 145 1

5 3 1000
1 2 20
4 5 40
3 2 30

উত্তর আসছে ঃ ২০+৪০+৩০+(১০০০*২)=২০৯০
আউটপুট ঃ Case 2: 2090 2




#include<bits/stdc++.h>
#define fr(i1,m) for(int i1=0;i1<m;i1++)
using namespace std;
struct edge
{
    int u,v,w;
    bool operator < ( const edge& p ) const
    {
        return w < p.w;
    }
};
int pr[100107],aa[100010];
long kk,f,g,h;
vector<edge>e;
int find(int r)
{
    return (pr[r]==r) ? r:  find(pr[r]);
}
int mst(int n)
{
    sort(e.begin(),e.end());
    for(int i=1; i<=n; i++)
        pr[i]=i;

    long long count=0,s=0;                                                                                                                                                           "Fuck\n";
    for(int i=0; i<(int)e.size(); i++)
    {
        int u=find(e[i].v);

        int v=find(e[i].u);

        if(u!=v)
        {
            pr[u]=v;
            count++;
            if(e[i].w>=h)
            {
                if(aa[v]==0)
                {
                    kk++;
                    aa[v]=1;
                }

                if(aa[u]==0)
                {
                    kk++;
                    aa[u]=1;
                }
            }
            else
                s+=e[i].w;
            if(count==n-1)
                break;
        }
    }
    return s;
}
vector<int>vc[100100];
long long ff[100008],l;
void bfs(int n)
{
    queue<int>q;

    q.push(n);

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

        ff[u]=1;

        if(aa[u]==1)
            l=1;

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

            if(ff[v]==0)
            {
                ff[v]=1;

                q.push(v);
            }
        }
        q.pop();
    }
}
int main()
{
    long  m;

    cin>>m;

    fr(ii,m)
    {
        long long i,u,v,w,cc=0;
        kk=0;

        cin>>f>>g>>h;

        for(i=1; i<=g; i++)
        {
            cin>>u>>v>>w;

            edge get;

            get.u=u;
            get.v=v;
            get.w=w;

            e.push_back(get);

            vc[u].push_back(v);

            vc[v].push_back(u);
        }
        long xx=mst(f);

        for(i=1; i<=f; i++)
        {
            if(ff[i]==0)
            {
                l=0;
                bfs(i);
                //cout<<i<<" "<<l<<"\n";
                if(l==0)
                    cc++;
            }
        }

        printf("Case %ld: ",ii+1);
        cout<<xx+kk*h+cc*h<<" "<<kk+cc<<"\n";
        e.clear();
        fr(i,f+3)
        {
            aa[i]=0;
            vc[i].clear();
            ff[i]=0;

        }
    }
    return 0;

}

UVA 12428 - Enemy at the Gates

///...................SUBHASHIS MOLLICK...................///
///.....DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING....///
///.............ISLAMIC UNIVERSITY,BANGLADESH.............///
///....................SESSION-(14-15)....................///
#include<bits/stdc++.h>
using namespace std;
#define sf(a) scanf("%lld",&a)
#define sf2(a,b) scanf("%lld %lld",&a,&b)
#define sf3(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)
#define pf(a) printf("%lld",a)
#define pf2(a,b) printf("%lld %lld",a,b)
#define pf3(a,b,c) printf("%lld %lld %lld",a,b,c)
#define nl printf("\n")
#define   timesave              ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define ll long long
#define pb push_back
#define MPI map<int,int>mp;
#define fr(i,n) for(i=0;i<n;i++)
#define fr1(i,n) for(i=1;i<=n;i++)
#define frl(i,a,b) for(i=a;i<=b;i++)
/*primes in range 1 - n
1 - 100(1e2) -> 25 pimes
1 - 1000(1e3) -> 168 primes
1 - 10000(1e4) -> 1229 primes
1 - 100000(1e5) -> 9592 primes
1 - 1000000(1e6) -> 78498 primes
1 - 10000000(1e7) -> 664579 primes
large primes ->
104729 1299709 15485863 179424673 2147483647 32416190071 112272535095293 48112959837082048697
*/
//freopen("Input.txt","r",stdin);
//freopen("Output.txt","w",stdout);
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
main()
{
    timesave;
    long ts;
    cin>>ts;
    while(ts--)
    {
        long n,m;
        cin>>n>>m;
        long total=n-1;
        m-=(n-1);
        long k=1;
        while(m>0)
        {
            m-=k;
            if(k==1)
                total-=2;
            else
                total--;
            k++;
        }
        cout<<total<<endl;
    }
}

UVA 12425 - Best Friend

///...................SUBHASHIS MOLLICK...................///
///.....DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING....///
///.............ISLAMIC UNIVERSITY,BANGLADESH.............///
///....................SESSION-(14-15)....................///
#include<bits/stdc++.h>
using namespace std;
#define sf(a) scanf("%lld",&a)
#define sf2(a,b) scanf("%lld %lld",&a,&b)
#define sf3(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)
#define pf(a) printf("%lld",a)
#define pf2(a,b) printf("%lld %lld",a,b)
#define pf3(a,b,c) printf("%lld %lld %lld",a,b,c)
#define nl printf("\n")
#define   timesave              ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define ll long long
#define pb push_back
#define MPI map<int,int>mp;
#define fr(i,n) for(i=0;i<n;i++)
#define fr1(i,n) for(i=1;i<=n;i++)
#define frl(i,a,b) for(i=a;i<=b;i++)
/*primes in range 1 - n
1 - 100(1e2) -> 25 pimes
1 - 1000(1e3) -> 168 primes
1 - 10000(1e4) -> 1229 primes
1 - 100000(1e5) -> 9592 primes
1 - 1000000(1e6) -> 78498 primes
1 - 10000000(1e7) -> 664579 primes
large primes ->
104729 1299709 15485863 179424673 2147483647 32416190071 112272535095293 48112959837082048697
*/
//freopen("Input.txt","r",stdin);
//freopen("Output.txt","w",stdout);
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
vector<ll> prime;
char vis[1000100];
#define sz 1000000
void sieve()
{
    prime.push_back(2);
    ll sqrtn = sqrt(sz),i,j;
    for(i=3; i<=sqrtn; i+=2)
    {
        if(vis[i]==0)
        {
            for(j=i*i; j<=sz; j+=2*i)
                vis[j]=1;
        }
    }
    for(i=3; i<=sz; i+=2)
        if(vis[i]==0)
            prime.push_back(i);
}
vector<ll>vec,vec1,phi;
ll calc(ll nm)
{
    ll res=nm,i;
    ll sqrtn=sqrt(nm);
    for(i=0; i<prime.size()&&prime[i]<=sqrtn; i++)
    {
        if(nm%prime[i]==0)
        {
            while((nm%prime[i])==0)
            {
                nm/=prime[i];
            }
            res/=prime[i];
            res*=prime[i]-1;
        }
    }
    if(nm!=1)
    {
        res/=nm;
        res*=nm-1;
    }
    return res;
}
main()
{
    timesave;
    sieve();
    long ts,cs=1;
    cin>>ts;
    while(ts--)
    {
        ll n,q,i,sq;
        cin>>n>>q;
        vec.clear();
        vec1.clear();
        phi.clear();
        sq=sqrt(n);

        for(i=1; i<=sq; i++)
        {
            if(n%i==0)
            {
                vec.push_back(i);
                if(n/i!=i)
                {
                    vec.push_back(n/i);
                }
            }
        }
        sort(vec.begin(),vec.end());
        vec1.clear();
        for(i=0; i<vec.size(); i++)
        {
            phi.push_back(calc(n/vec[i]));
            if(i)
            {
                phi[i]+= phi[i-1];/// for comulative sum
            }
        }
        ll nm;
        printf("Case %ld\n",cs++);
        for(i=1; i<=q; i++)
        {
            cin>>nm;
            if(nm>=n)
            {
                printf ( "%lld\n", n );/// sob guloi answer
                continue;
            }
            if(nm<1)
            {
                printf ( "%lld\n", 0 );///kono tai ans hobe na
                continue;
            }
            ll pos =upper_bound(vec.begin(),vec.end(),nm )-vec.begin();
            pos--;
            printf ( "%lld\n", phi[pos] );
        }
    }
}

UVA 12791 - Lap

#include <cstdio>

int main()
{
  int X, Y;
  while (scanf("%d %d", &X, &Y) != EOF) {
    int d = Y - X;
    int lap = Y / d;
    if (Y % d)
      lap++;
    printf("%d\n", lap);
  }
  return 0;
}

UVA 571 Jugs

///...................SUBHASHIS MOLLICK...................///
///.....DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING....///
///.............ISLAMIC UNIVERSITY,BANGLADESH.............///
///....................SESSION-(14-15)....................///
#include<bits/stdc++.h>
using namespace std;
#define sf(a) scanf("%lld",&a)
#define sf2(a,b) scanf("%lld %lld",&a,&b)
#define sf3(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)
#define pf(a) printf("%lld",a)
#define pf2(a,b) printf("%lld %lld",a,b)
#define pf3(a,b,c) printf("%lld %lld %lld",a,b,c)
#define nl printf("\n")
#define   timesave              ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define ll long long
#define pb push_back
#define MPI map<int,int>mp;
#define fr(i,n) for(i=0;i<n;i++)
#define fr1(i,n) for(i=1;i<=n;i++)
#define frl(i,a,b) for(i=a;i<=b;i++)
/*primes in range 1 - n
1 - 100(1e2) -> 25 pimes
1 - 1000(1e3) -> 168 primes
1 - 10000(1e4) -> 1229 primes
1 - 100000(1e5) -> 9592 primes
1 - 1000000(1e6) -> 78498 primes
1 - 10000000(1e7) -> 664579 primes
large primes ->
104729 1299709 15485863 179424673 2147483647 32416190071 112272535095293 48112959837082048697
*/
//freopen("Input.txt","r",stdin);
//freopen("Output.txt","w",stdout);
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
long pre[1005][1005][4],vis[1005][1005];
struct NODE
{
    long a,b;
};
NODE node,node1;
queue<NODE>q;
long ca,cb,n,k;
void call(long num)
{
    if(vis[node1.a][node1.b]==0)
    {
        vis[node1.a][node1.b]=1;
        pre[node1.a][node1.b][0]=num;
        pre[node1.a][node1.b][1]=node.a;
        pre[node1.a][node1.b][2]=node.b;
        q.push(node1);
    }
}
void print(long aa,long bb)
{
    if(aa==0&&bb==0)
        return;
    print(pre[aa][bb][1],pre[aa][bb][2]);
    k=pre[aa][bb][0];
    if(k==1)
    {
        cout<<"fill A"<<endl;
    }
    else if(k==2)
    {
        cout<<"fill B"<<endl;
    }
    else if(k==3)
    {
        cout<<"empty A"<<endl;
    }
    else if(k==4)
    {
        cout<<"empty B"<<endl;
    }
    else if(k==5)
    {
        cout<<"pour A B"<<endl;
    }
    else if(k==6)
    {
        cout<<"pour B A"<<endl;
    }
}
main()
{
    timesave;
    while(cin>>ca>>cb>>n)
    {
        memset(vis,0,sizeof(vis));
        node.a=0;
        node.b=0;
        vis[0][0]=1;
        q.push(node);
        while(!q.empty())
        {
            node=q.front();
            q.pop();
            if(node.b==n)
                break;
            node1.a=ca;
            node1.b=node.b;
            call(1);
            node1.a=node.a;
            node1.b=cb;
            call(2);
            node1.a=0;
            node1.b=node.b;
            call(3);
            node1.a=node.a;
            node1.b=0;
            call(4);
            k=min(cb-node.b,node.a);
            node1.a=node.a-k;
            node1.b=node.b+k;
            call(5);
            k=min(ca-node.a,node.b);
            node1.a=node.a+k;
            node1.b=node.b-k;
            call(6);
        }
        print(node.a,node.b);
        cout<<"success"<<endl;
        while(!q.empty())
            q.pop();
    }
}

Maximum length of the longest street in the city by using BFS

How to find maximum  length of the longest street in the city by using BFS

Problem link:  https://www.spoj.com/problems/BENEFACT/

Input:
1
6
1 2 3
2 3 4
2 6 2
6 4 6
6 5 5

Output:
12

Explanation:
6+2+4=12
At first start bfs from 1 and find the longest city from 1
And again start with bfs from this longest city and find the longest length
So we need two bfs search.

1st Code:

///...................SUBHASHIS MOLLICK...................///
///.....DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING....///
///.............ISLAMIC UNIVERSITY,BANGLADESH.............///
///....................SESSION-(14-15)....................///
#include<bits/stdc++.h>
using namespace std;
#define sf(a) scanf("%lld",&a)
#define sf2(a,b) scanf("lld%lld",&a,&b)
#define sf3(a,b,c) scanf("lld%lld%lld",&a,&b,&c)
#define pf(a) printf("%lld",a)
#define pf2(a,b) printf("lld%lld",a,b)
#define pf3(a,b,c) printf("lld%lld%lld",a,b,c)
#define nl printf("\n")
#define ll long long
#define pb push_back
#define MPI map<int,int>mp
#define fr(i,n) for(i=0;i<n;i++)
#define fr1(i,n) for(i=1;i<=n;i++)
#define frl(i,a,b) for(i=a;i<=b;i++)
//freopen("Input.txt","r",stdin);
//freopen("Output.txt","w",stdout);
vector<long>vec[50005],cost[50005];
long vis[50005];
long bfs(long source)
{
    queue<long>q;
    memset(vis,0,sizeof(vis));
    long dist[50005]= {0},boroman=0,mx=0;
    dist[source]=0;
    vis[50005]=1;
    q.push(source);
    long i;
    while(!q.empty())
    {
        long u=q.front();
        if(mx<dist[u])
        {
            mx=dist[u];
            boroman=u;
        }
        for(i=0; i<vec[u].size(); i++)
        {
            long v=vec[u][i];
            if(vis[v]==0)
            {
                dist[v]=dist[u]+cost[u][i];
                vis[v]=1;
                q.push(v);
            }
        }
        q.pop();
    }
    return boroman;
}
long bfss(long source)
{
    memset(vis,0,sizeof(vis));
    queue<long>q;
    long dist[50005]= {0},i,mx=0;
    q.push(source);
    vis[source]=1;
    dist[source]=0;
    while(!q.empty())
    {
        long u=q.front();
        vis[u]=1;
        if(mx<dist[u])
        {
            mx=dist[u];
        }
        for(i=0; i<vec[u].size(); i++)
        {
            long v=vec[u][i];
            if(vis[v]==0)
            {
                dist[v]=dist[u]+cost[u][i];
                // mx=max(mx,dist[v]);
                vis[v]=1;
                q.push(v);
            }
        }
        q.pop();
    }
    return mx;
}
main()
{
    long ts;
    cin>>ts;
    while(ts--)
    {
        long n,u,v,d,i;
        cin>>n;
        for(i=1; i<n; i++)
        {
            cin>>u>>v>>d;
            vec[u].push_back(v);
            vec[v].push_back(u);
            cost[u].push_back(d);
            cost[v].push_back(d);
        }
        long boro=bfs(1);
        cout<<bfss(boro)<<endl;
        for(i=0; i<=50005; i++)
        {
            vec[i].clear();
            cost[i].clear();
            vis[i]=0;
        }
    }

}

2nd Code:

#include<iostream>
#include<string>
#include<cmath>
#include<algorithm>
#include<vector>
#include<map>
#include<stack>
#include<cctype>
#include<cmath>
#include<cstring>
#include<queue>
#include<cstdio>
#include<sstream>
using namespace std;
#define pb push_back
#define pi 3.141592653589793238462643383

int dist[50001];
int visited[50001];
int n;
struct node
{
    int i,d;
};
typedef struct node node;
vector<node> v[50001];
int bfs(int start){
    queue<int> q;
    q.push(start);
    int i,j;
    for(i=0;i<=n;i++){
        visited[i]=0;
        dist[i]=0;
    }
    visited[start]=1;
    while(!q.empty()){
        int temp = q.front();
        q.pop();
        for(i=0;i<v[temp].size();i++){
            if(visited[v[temp][i].i]==0){
                visited[v[temp][i].i]=1;
                dist[v[temp][i].i]+=dist[temp]+v[temp][i].d;
                q.push(v[temp][i].i);
            }
        }
    }
    return int(max_element(dist+1,dist+n+1)-dist);
}
int main()
{
 int i,j,t,u1,v1,d;
 node temp;
 scanf("%d",&t);
 while(t>0){
        scanf("%d",&n);
        for(i=1;i<=n;i++)
            v[i].clear();
        for(i=1;i<=n-1;i++){
                scanf("%d%d%d",&u1,&v1,&d);
                temp.i =  v1;
                temp.d = d;
                v[u1].pb(temp);
                temp.i = u1;
                v[v1].pb(temp);
        }
        int start = bfs(1);
        cout<<start<<endl;
        int ans = bfs(start);
        printf("%d\n",dist[ans]);
        t--;
    }
}

UVA 11988 - Broken Keyboard

#include <cstdio>
#include <list>
#include <cstring>
using namespace std;
int main()
{
    char line[100001];
    while (scanf("%s", line) != EOF)
    {
        list<char> l;
        int len = strlen(line);
        list<char>::iterator it = l.begin();
        for (int i = 0; i < len; i++)
        {
            if (line[i] == '[')
            {
                it = l.begin();
            }
            else if (line[i] == ']')
            {
                it = l.end();
            }
            else
            {
                l.insert(it, line[i]);
            }   
        }
        for (it = l.begin(); it != l.end(); it++)
        {
            printf("%c", *it);
        }
        printf("\n");
    }
    return 0;
}