924 - Spreading the News

[nymo]

Hi, I have implemented simple BFS for this problem, but get WA. Is this a correct approach? Can someone provide some IOs? thanks.

[Jan]

I used dfs. But bfs should be ok, too. Try the sample

Input:

Code: Select all

5
2 3 4
0
0
0
0
5
0
1
2
3
4

Output:

Code: Select all

2 1
0
0
0
0

Hope it helps.

[nymo]

My code passes that sample, still WA
[EDIT] found the error... ACC now,

[jan_holmes]

Can you give me another sample IOs ?

I got WA with this code :

Code: Select all

#include <iostream>
#include <bitset>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <cstring>
#include <vector>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <cctype>
#include <set>
#include <cmath>
#include <climits>
#include <sstream>
#include <fstream>
#include <list>
#include <functional>
#include <utility>
#include <iomanip>
#include <ctime>

using namespace std;

#define SZ size()
#define pp push_back

typedef long long LL;
typedef vector <int> vi;
typedef vector <double> vd;
typedef vector <vi> vvi;
typedef vector <string> vs;
typedef pair<int,int> pii;
typedef vector <LL> vll;

bool stat[5000];
int dd[50000];
vvi v(2501);
int ret,day;

//WA

void doit(int start, int days) {
    int temp = 0;
    stat[start] = true;
    for (int i=0;i<v[start].SZ;i++) {
        if (stat[v[start][i]]) continue;
        temp++;
    }
    dd[days]+=temp;
    if (dd[days] > ret) {
             ret = dd[days];
             day = days+1;
    }
    else if (dd[days] == ret && (days+1) < day) {
         day = days+1;
    }
    for (int i=0;i<v[start].SZ;i++) {
        if (stat[v[start][i]]) continue;
        doit(v[start][i],days+1);
    }
    return ;
}
           

int main () {
    //freopen("news.in","r",stdin);
    //freopen("news.out","w",stdout);
    int n,m,k,r;
    int cases;
    scanf("%d",&n);
    v.clear();
    for (int i=0;i<n;i++) {
        scanf("%d",&m);
        for(int j=0;j<m;j++) { scanf("%d",&r); v[i].pp(r);}
    }
    scanf("%d",&cases);
    for (int i=0;i<cases;i++) {
        ret = 0;
        day = INT_MAX;
        scanf("%d",&k);
        memset(dd,0,sizeof(dd));
        memset(stat,false,sizeof(stat));
        stat[k] = true;
        doit(k,0);
        if (ret) printf("%d %d\n",ret,day);
        else printf("%d\n",0);
    }
    return 0;
}
   


[himanshu]

The following works for the sample posted in this thread but the judge gives WA.

Code: Select all

#include<iostream>
#include<map>
#include<list>
#include<queue>
#include<algorithm>

void post_process(std::map<int, int>& d, std::map<int, int>& p)
{
   // count how many times each depth appears
   std::map<int, int> c;   
   
   for(int u = 0; u < p.size(); u++)
      c[d[u]]++;
         
   // find the depth that appears max times   
   std::map<int, int>::iterator i = c.begin();
   std::pair<int, int> max_boom = *i;   
   while(++i != c.end())
      if(i->second > max_boom.second)
         max_boom = *i;   
   std::cout << max_boom.second << ' ' << max_boom.first << std::endl;
}

void bfs(std::map< int, std::list<int> >& g, int s)
{
   enum {WHITE, GRAY, BLACK};
   std::map<int, int> color;
   std::map<int, int> d;
   std::map<int, int> p;
   int u;

   for(u = 0; u < g.size(); u++)
      if(u != s)
      {
         color[u] = WHITE;
         d[u]     = 32767;
         p[u]     = -1;
      }

   color[s] = GRAY;
   d[s] = 0;
   p[s] = -1;

   std::queue<int> q;
   q.push(s);   
   while(!q.empty())
   {      
      int u = q.front(); q.pop();      
      for( std::list<int>::iterator v = g[u].begin(); v != g[u].end(); v++)
      {
         if(color[*v] == WHITE)
         {
            color[*v] = GRAY;
            d[*v] = d[u] + 1;
                p[*v] = u;
                q.push(*v);      
         }           
      }
      color[u] = BLACK;      
   }
   
   post_process(d, p);
}

int main()
{
   std::map< int, std::list<int> > m;
   
   int E;
   std::cin >> E;
   for(int i = 0; i < E; i++)
   {
      int nf, f;
      std::cin >> nf;
      
      m[i];// so that the vertex is registered
          // even if there are no edges
      while(nf--)
      {
         std::cin >> f;
         m[i].push_back(f);
      }
   }
   int T;
   std::cin >> T;
   while(T--)
   {
      int s;
      std::cin >> s;
      // if there are no edges from the source
      if(m[s].size() == 0)
         std::cout << 0 << std::endl;
      else
         bfs(m, s);
   }
   return 0;   
}

Please help.

Thank You,
HG

[Jan]

Try the set.

Input:

Code: Select all

5
2 1 2
2 3 4
1 0
1 4
0
1
3

Output:

Code: Select all

1 1

Hope it helps.

[himanshu]

You are amazing. May I ask you the secret.

Thank You,
++imanshu

[Jan]

You are amazing. May I ask you the secret.

Thanks.. No secrets...

Don't forget to remove your code.

[emotional blind]

You are amazing. May I ask you the secret.

Thanks.. No secrets...

One open secret: Lot of practice.

[মেহেদী সবুজ]

Thanks brianfry713

Code: Select all

Remove after ACCEPTED


[brianfry713]

Input:

Code: Select all

9
3 7 5 8
2 0 6
2 3 7
0
2 8 6
0
6 1 2 5 8 7 3
1 6
2 6 3
1
2

Answer should be 3 3

[brianfry713]

Input

Code: Select all

6
2 1 2
2 3 4
3 0 4 5
1 4
1 4
2 0 2
1
4

Output should be 0

[brianfry713]

Input:

Code: Select all

7
0
1 6
2 4 1
5 1 6 5 3 0
1 1
2 6 0
1 5
7
0
1
2
3
4
5
6

AC output:

Code: Select all

0
1 1
2 1
4 1
1 1
2 1
1 1

[raiyan21]

My code gives correct output for every input case described here and in the problem statement. But still WA. Someone please help. Here is my code.

Code: Select all

Code removed after AC


I got the mistake. thanks brianfry

[brianfry713]

Input:

Code: Select all

7
0
1 6
2 4 1
5 1 6 5 3 0
1 1
2 6 0
1 5
7
0
1
2
3
4
5
6

AC output:

Code: Select all

0
1 1
2 1
4 1
1 1
2 1
1 1