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

Removed.

Note: The judge's data doesn't contain any self-edges.

[brianfry713]

Input:

Code: Select all

Removed.

Note: The judge's data doesn't contain any self-edges.

[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]

Removed.

Note: The judge's data doesn't contain any self-edges.