Page 1 of 2

11518 - Dominos 2

Posted: Fri Mar 06, 2009 12:53 pm
by vahid sanei
I get TLE , Please help me
here is my code :

Code: Select all

REMOVED 

Re: 11518 - Dominos 2

Posted: Fri Mar 06, 2009 8:21 pm
by Jan
Just think that, you can run the bfs or dfs only once. As I see that you are calling the bfs l times.

Re: 11518 - Dominos 2

Posted: Sat Mar 07, 2009 6:35 am
by 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

Re: 11518 - Dominos 2

Posted: Sat Mar 07, 2009 6:51 am
by 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.

Re: 11518 - Dominos 2

Posted: Sat Mar 07, 2009 7:00 am
by vahid sanei
Thanks Jan :D

Re: 11518 - Dominos 2

Posted: Sat Apr 04, 2009 5:53 pm
by 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;
}

Re: 11518 - Dominos 2

Posted: Sun Oct 10, 2010 5:01 pm
by saiful_sust
Hi tanmoy...You just made a silly mistake...

Check ur bool map array !!!!!!!!!!! :D :D :D
  • IMPOSSIBLE MEANS I M POSSIBLE....

Re: 11518 - Dominos 2

Posted: Wed Oct 20, 2010 9:50 am
by Shafaet_du
Run simple dfs. Be very careful about flagging. if one domino has fallen,it cant fall once again :wink:

Re: 11518 - Dominos 2

Posted: Wed Nov 03, 2010 9:11 pm
by 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.

Re: 11518 - Dominos 2

Posted: Sat Jan 22, 2011 7:56 pm
by 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;

}

Re: 11518 - Dominos 2

Posted: Thu Nov 03, 2011 11:18 am
by 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.

Re: 11518 - Dominos 2

Posted: Mon Nov 21, 2011 5:34 pm
by 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.

Re: 11518 - Dominos 2

Posted: Thu May 17, 2012 9:49 pm
by mahade hasan
cutt>>>ACC

Re: 11518 - Dominos 2

Posted: Fri May 18, 2012 12:23 am
by brianfry713
If Mat can only be 0 or 1 then make it type bool.

Re: 11518 - Dominos 2

Posted: Fri May 18, 2012 7:28 pm
by mahade hasan
thanx for ur kind reply
Can You give some I/O?