11518 - Dominos 2

[vahid sanei]

I get TLE , Please help me
here is my code :

Code: Select all

REMOVED 

[Jan]

Just think that, you can run the bfs or dfs only once. As I see that you are calling the bfs l times.

[vahid sanei]

Just think that, you can run the bfs or dfs only once. As I see that you are calling the bfs l times.

how ?
if sources be different
like this:

Code: Select all

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

ans is 2+3=5

[Jan]

Sorry. I actually wanted to say that

Code: Select all

int bfs(int i,vector< vector < int > > a)

In this line when bfs is called then all the values will be copied in vector< vector < int > > a. So, each time a bfs is called, a huge number of values will be copied. So, you can store 'a' as global or simply pass the reference, then only the address will be provided not the whole values. Just change the line to

Code: Select all

int bfs(int i,vector< vector < int > > &a) // Check that the reference is passed

Hope it helps.

[vahid sanei]

Thanks Jan

[tanmoy]

anyone help plz i'm getting WA for this problem.

Code: Select all

#include<stdio.h>
#include<string.h>
#include<vector>
#include<list>
using namespace std;
#define _pf printf
#define _sc scanf
#define max 10002
int n,m,l,C;
list<int> L[max];
bool map[max];
bool check[max];

void dfs(int i){
	int r;
	C++;
	map[i]=false;
	list<int>::iterator It;
	for(It=L[i].begin();It!=L[i].end();It++){
		r=(*It);
		if(map[r]){
			dfs(r);
		}
	}
}


int main(){
	int T,x,y,z,S;
	_sc("%d",&T);
	while(T--){
		memset(map,true,sizeof(map));
		memset(check,true,sizeof(check));
		S=0;
		_sc("%d %d %d",&n,&m,&l);
		while(m--){
			_sc("%d %d",&x,&y);
			if(x>n || y>n) continue;
			L[x].push_back(y);
		}

		while(l--){
			_sc("%d",&z);
			if(z>n)continue;
			if(check[z]){
				C=0;
				check[z]=false;
				dfs(z);
				S+=C;
			}
		}
		_pf("%d\n",S);
		for(int i=0;i<max;i++)
		L[i].clear();
	}


	return 0;
}

[saiful_sust]

Hi tanmoy...You just made a silly mistake...

Check ur bool map array !!!!!!!!!!!

• IMPOSSIBLE MEANS I M POSSIBLE....

[Shafaet_du]

Run simple dfs. Be very careful about flagging. if one domino has fallen,it cant fall once again

[zobayer]

Note:

Each of the following l lines contains a single integer z indicating that the domino numbered z is knocked over by hand.

Here, z's aren't unique.

[receme]

I get TLE...Help me...I can't understand how can I reduce the time....here is my code....

#include<stdio.h>
#include <iostream>
#include <queue>
using namespace std;

int r,s,i,j,k,n,m,cas,l,l1,N,G[10001][10001],co,v[10001],flag,f[10001],lp;
queue<int> q;

void BFS(int start_v, int n)
{
v[start_v]=1;

for(int i = 0; i < n; i++) {
if(G[start_v] == 1 && v == 0)
{ q.push(i);
v = 1;
co++;
}
}
while(!q.empty())
{
int tmp = q.front();
q.pop();
BFS(tmp,n);
}
}


int main(){

scanf("%d",&cas);

for(l1=0;l1<cas;l1++){

scanf("%d %d %d",&N,&m,&l);

for(i=0;i<N;i++)
for(j=i;j<N;j++)
G[j]=G[j]=0;

for(i=0;i<m;i++){
scanf("%d %d",&r,&s);
G[r-1][s-1]=1;
}

for(i=0;i<l;i++){
scanf("%d",&co);
f=co-1;
}


for(i=0;i<N;i++)
v=0;
lp=l;
co=0;
for(k=0;k<l;k++){

j=f[k];
if(v[j]==1){
lp--;
continue;}
v[j]=1;

BFS(j,N);

}
printf("%d\n",co+lp);



}

return 0;

}

[marjan]

Keep an array of Domino objects. Each one has a boolean indicating whether or not it has been knocked down, and a stack of integers that are the indices of the dominoes that it will knock down.
Then for each domino that's knocked down, run a recursive function that knocks down all dominoes that are in the first domino's stack. Don't knock down dominoes that have previously been knocked down. For each domino knocked down, increment a running total.

[outsbook]

Run BFS single time for all domino's which are knocked over by hand.
If you run BFS l time then you got time limit exit.

First push all z to queue then run bfs one time and calculate total number of domino's fall down.

[mahade hasan]

cutt>>>ACC

[brianfry713]

If Mat can only be 0 or 1 then make it type bool.

[mahade hasan]

thanx for ur kind reply
Can You give some I/O?