শনিবার, ২৮ অক্টোবর, ২০১৭

UVA 924 Spreading the News

#include<bits/stdc++.h>
using namespace std;
vector<long>vec[2505];
long dist[2505];
long bfs(long s)
{
    memset(dist,-1,sizeof(dist));
    queue<long>q;
    q.push(s);
    dist[s]=0;
    long u,v,i1;
    while(!q.empty())
    {
        u=q.front();
        q.pop();
        for(i1=0;i1<vec[u].size();i1++)
        {
            v=vec[u][i1];
            if(dist[v]==-1)
            {
                dist[v]=dist[u]+1;
                q.push(v);
            }
        }
    }
}
main()
{
    long n;
    while(cin>>n)
    {
        long i,a,j,b;
        for(i=0;i<n;i++)
        {
            cin>>a;
            for(j=1;j<=a;j++)
            {
                cin>>b;
                vec[i].push_back(b);
            }
        }
        long ts,x;
        cin>>ts;
        while(ts--)
        {
            cin>>x;
            bfs(x);
            sort(dist,dist+n);
            long day,mx,cs;
            day=mx=i=0;
            for(i=0; i<n; i++)
            {
                j=i;
                cs=0;
                while(dist[i]==dist[j])
                {
                    if(dist[j]>0)
                    cs++;
                    j++;
                }
                if(cs>mx)
                {
                    mx=cs;
                    day=dist[i];
                }
                i=j-1;
            }
            if(dist[n-1]==0)
                cout<<0<<endl;
            else
                cout<<mx<<" "<<day<<endl;
        }
        for(i=0;i<n;i++)
            vec[i].clear();
    }
}

কোন মন্তব্য নেই:

একটি মন্তব্য পোস্ট করুন

Factorization with prime Sieve

vector <int> prime; char sieve[1000009]; int N=1000009; void primeSieve ( ) { sieve[0] = sieve[1] = 1; prime.push_back(2); ...