924 - Spreading The News

All about problems in Volume 9. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

nymo
Experienced poster
Posts: 149
Joined: Sun Jun 01, 2003 8:58 am
Location: :)

924 - Spreading The News

Post by nymo » Sun Nov 12, 2006 12:14 pm

Hi, I have implemented simple BFS for this problem, but get WA. Is this a correct approach? Can someone provide some IOs? thanks.
Last edited by nymo on Sat May 19, 2007 8:06 pm, edited 1 time in total.
regards,
nymo

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Sun Nov 12, 2006 1:41 pm

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.
Ami ekhono shopno dekhi...
HomePage

nymo
Experienced poster
Posts: 149
Joined: Sun Jun 01, 2003 8:58 am
Location: :)

Post by nymo » Sun Nov 12, 2006 3:05 pm

My code passes that sample, still WA :(
[EDIT] found the error... ACC now, :D
regards,
nymo

jan_holmes
Experienced poster
Posts: 136
Joined: Fri Apr 15, 2005 3:47 pm
Location: Singapore
Contact:

Post by jan_holmes » Tue Jun 26, 2007 5:43 pm

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
New poster
Posts: 17
Joined: Mon May 15, 2006 12:24 pm
Location: Hyderabad, India
Contact:

924 WA

Post by himanshu » Tue Nov 06, 2007 7:05 pm

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
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Fri Nov 09, 2007 9:57 pm

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.
Ami ekhono shopno dekhi...
HomePage

himanshu
New poster
Posts: 17
Joined: Mon May 15, 2006 12:24 pm
Location: Hyderabad, India
Contact:

Amazing

Post by himanshu » Wed Nov 14, 2007 2:16 pm

You are amazing. May I ask you the secret.

Thank You,
++imanshu

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Re: Amazing

Post by Jan » Wed Nov 14, 2007 7:53 pm

himanshu wrote:You are amazing. May I ask you the secret.
Thanks.. :D No secrets...

Don't forget to remove your code.
Ami ekhono shopno dekhi...
HomePage

User avatar
emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

Re: Amazing

Post by emotional blind » Wed Mar 05, 2008 5:01 pm

Jan wrote:
himanshu wrote:You are amazing. May I ask you the secret.
Thanks.. :D No secrets...
One open secret: Lot of practice. :D

?????? ????
New poster
Posts: 7
Joined: Tue Apr 03, 2012 2:34 pm
Location: Manikgonj, Bangladesh

Re: 924 - Spreading the News

Post by ?????? ???? » Wed Sep 26, 2012 9:01 am

Thanks brianfry713

Code: Select all

Remove after ACCEPTED
Last edited by ?????? ???? on Thu Sep 27, 2012 10:31 am, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 924 - Spreading the News

Post by brianfry713 » Thu Sep 27, 2012 1:35 am

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
Check input and AC output for thousands of problems on uDebug!

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 924 - Spreading the News

Post by brianfry713 » Wed Jan 23, 2013 10:08 pm

Input

Code: Select all

Removed.
Note: The judge's data doesn't contain any self-edges.
Check input and AC output for thousands of problems on uDebug!

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 924 - Spreading the News

Post by brianfry713 » Thu Jan 24, 2013 8:50 pm

Input:

Code: Select all

Removed.
Note: The judge's data doesn't contain any self-edges.
Check input and AC output for thousands of problems on uDebug!

raiyan21
New poster
Posts: 2
Joined: Wed Jan 30, 2013 12:08 pm

Re: 924 - Spreading the News

Post by raiyan21 » Wed Jan 30, 2013 12:14 pm

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 :)
Last edited by raiyan21 on Wed Jan 30, 2013 11:50 pm, edited 2 times in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 924 - Spreading the News

Post by brianfry713 » Wed Jan 30, 2013 9:27 pm

brianfry713 wrote: Removed.
Note: The judge's data doesn't contain any self-edges.
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 9 (900-999)”