924 - Spreading The News
Moderator: Board moderators
924 - Spreading The News
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
nymo
I used dfs. But bfs should be ok, too. Try the sample
Input:
Output:
Hope it helps.
Input:
Code: Select all
5
2 3 4
0
0
0
0
5
0
1
2
3
4
Code: Select all
2 1
0
0
0
0
Ami ekhono shopno dekhi...
HomePage
HomePage
-
- Experienced poster
- Posts: 136
- Joined: Fri Apr 15, 2005 3:47 pm
- Location: Singapore
- Contact:
Can you give me another sample IOs ?
I got WA with this code :
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;
}
924 WA
The following works for the sample posted in this thread but the judge gives WA.
Please help.
Thank You,
HG
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;
}
Thank You,
HG
Try the set.
Input:
Output:
Hope it helps.
Input:
Code: Select all
5
2 1 2
2 3 4
1 0
1 4
0
1
3
Code: Select all
1 1
Ami ekhono shopno dekhi...
HomePage
HomePage
Amazing
You are amazing. May I ask you the secret.
Thank You,
++imanshu
Thank You,
++imanshu
Re: Amazing
Thanks..himanshu wrote:You are amazing. May I ask you the secret.
![:D](./images/smilies/icon_biggrin.gif)
Don't forget to remove your code.
Ami ekhono shopno dekhi...
HomePage
HomePage
-
- A great helper
- Posts: 383
- Joined: Mon Oct 18, 2004 8:25 am
- Location: Bangladesh
- Contact:
Re: Amazing
One open secret: Lot of practice.Jan wrote:Thanks..himanshu wrote:You are amazing. May I ask you the secret.No secrets...
![:D](./images/smilies/icon_biggrin.gif)
-
- New poster
- Posts: 7
- Joined: Tue Apr 03, 2012 2:34 pm
- Location: Manikgonj, Bangladesh
Re: 924 - Spreading the News
Thanks brianfry713
Code: Select all
Remove after ACCEPTED
Last edited by ?????? ???? on Thu Sep 27, 2012 10:31 am, edited 1 time in total.
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 924 - Spreading the News
Input:Answer should be 3 3
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
Check input and AC output for thousands of problems on uDebug!
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 924 - Spreading the News
Input
Note: The judge's data doesn't contain any self-edges.
Code: Select all
Removed.
Check input and AC output for thousands of problems on uDebug!
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 924 - Spreading the News
Input:
Note: The judge's data doesn't contain any self-edges.
Code: Select all
Removed.
Check input and AC output for thousands of problems on uDebug!
Re: 924 - Spreading the News
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.
I got the mistake. thanks brianfry ![:)](./images/smilies/icon_smile.gif)
Code: Select all
Code removed after AC
![:)](./images/smilies/icon_smile.gif)
Last edited by raiyan21 on Wed Jan 30, 2013 11:50 pm, edited 2 times in total.
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 924 - Spreading the News
Note: The judge's data doesn't contain any self-edges.brianfry713 wrote: Removed.
Check input and AC output for thousands of problems on uDebug!