924 - Spreading The News

[katana1]

following is my code;i am new to coding;i debugged my code for two entire night still cant understand why its giving tle(for case 2ie when source is 2 and 4) and rte(for source 5) for following test case;

Code: Select all

Removed.

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



i am pasting my code here ;please its a sincere req to anyone of u to pls kindly explain the reasons of tle and rte as my debuging passes them;its also a rqst to go through my code and reply soon


using namespace std;
#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#define FOR(i,N)for(i=0;i<(N);i++)
vector<int>v[2500];
vector<int>vec(2500);
bool vis[2500];
int n,m,i,c,k,test,ca,sum,day,emp,endcount,maximum,l,flag;
void init()
{
FOR(i,n)
{

vis=false;
vec[i+1]=0;
}

sum=0;
day=1;
emp=0;
endcount=0;
flag=0;


}
void cal(int ca)
{
std::queue<int>q;
init();
if(v[ca][0]==0)
return;
vis[ca]=true;
++endcount;
for(i=1;i<v[ca].size();i++)
{
if(v[ca][1]==ca)
return;
q.push(v[ca]);
vis[v[ca]]=true;
++emp;
++endcount;
flag=1;
}
vec[day]=emp;
emp=0;
while(v[ca][0]--)
{
m=q.front();
for(i=1;i<v[m].size();i++)
{
if(!vis[v[m]])
{
q.push(v[m]);
vis[v[m]]=true;
++endcount;
++emp;
flag=1;
}
}
q.pop();
}
vec[++day]=emp;
if(endcount==n)
return;
while(!q.empty())
{
emp=0;
m=q.front();
while(v[m][0]--)
{
for(i=1;i<v[m].size();i++)
{

if(!vis[v[m]])
{
q.push(v[m]);
vis[v[m]]=true;
++endcount;
++emp;
flag=1;

}


}

}
q.pop();
vec[++day]=emp;
if(endcount==n)
return;

}
if(q.empty()) return;

}
int main()
{
//int n,i,c,k,test,ca;
scanf("%d",&n);
//std::vector<int>v[n];
for(i=0;i<n;i++)
{
scanf("%d",&c);
v.push_back(c);
while(c--)
{
scanf("%d",&k);
v[i].push_back(k);

}
}

/* for(i=0;i<n;i++)
{
for(int j=0;j<v[i].size();j++)
printf("%d ",v[i][j]);


}*/

scanf("%d",&test);
while(test--)
{

scanf("%d",&ca);
cal(ca);
if(flag==0)
printf("0\n");
else
{
maximum=0;
for(i=1;i<n;i++)
{
if(vec[i]>maximum)
{
maximum=vec[i];
l=i;

}
}

printf("%d %d\n",maximum,l);





}
}

return 0;
}

[brianfry713]

Try adding debug print statements into your code, and then later comment them out once you fix your bug. For example, put this before line 73:
printf("m = %d, v[m][0] = %d\n", m, v[m][0]);

[mohrd]

Why WA with this BFS?
All samples on this board passed.

Code: Select all

#include <stdio.h>
#include <list>
#include <vector>
#include <queue>
#include <iostream>

using namespace std;

typedef struct {
	int nvertices;
	int nedges;
	vector<list<int> > edges;
} graph;

void init_graph(graph *g) {
	g->nedges = 0;
	g->edges.resize(g->nvertices + 5);
}

void insert_edge(graph *g, int x, int y, bool directed) {
	g->edges[x].push_back(y);

	if (!directed) {
		insert_edge(g, y, x, true);
	} else {
		g->nedges++;
	}
}

void read_graph(graph *g, bool directed) {
	int fr, m;
	cin >> g->nvertices;
	init_graph(g);

	for (int i = 0; i < g->nvertices; i++) {
		cin >> m;
		for (; m > 0; m--) {
			cin >> fr;
			insert_edge(g, i, fr, directed);
		}
	}
}

////////////////////////////////////////////////////////

int firstDay, maxAll;

void bfs(graph *g, int v) {
	queue<int> q;
	vector<bool> visited(g->nvertices + 1);
	vector<int> parent(g->nvertices + 1);
	vector<int> days(g->nvertices + 1);

	q.push(v);
	visited[v] = true;
	parent[v] = -1;

	int counter, z = 0, lastParent = parent[v];

	list<int>::iterator li;
	while (!q.empty()) {
		v = q.front();
		q.pop();
		visited[v] = true;
		counter = 0;
		for (li = g->edges[v].begin(); li != g->edges[v].end(); li++) {
			if (visited[*li] != true) {
				q.push(*li);
				visited[*li] = true;
				parent[*li] = v;
				counter++;
			}
		}
		if (lastParent != parent[v]) {
			z++;
			lastParent = parent[v];
		}
		days[z] += counter;
	}

	maxAll = 0;
	for (int i = 0; i < g->nvertices; i++) {
		if (days[i] > maxAll) {
			maxAll = days[i];
			firstDay = i + 1;
		}
	}
}

int main() {
	graph g;

	read_graph(&g, true);

	int n, x;

	cin >> n;
	for (; n > 0; n--) {

		cin >> x;
		bfs(&g, x);

		cout << maxAll;
		if (maxAll > 0) {
			cout << " " << firstDay;
		}
		cout << endl;
	}

	return 0;
}