## 11518 - Dominos 2

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

Moderator: Board moderators

vahid sanei
Learning poster
Posts: 84
Joined: Fri Jan 09, 2009 4:37 pm
Location: IRAN

### 11518 - Dominos 2

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

Code: Select all

``````REMOVED
``````
Last edited by vahid sanei on Sat Mar 07, 2009 6:59 am, edited 1 time in total.
Impossible says I`m possible

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

### Re: 11518 - Dominos 2

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

vahid sanei
Learning poster
Posts: 84
Joined: Fri Jan 09, 2009 4:37 pm
Location: IRAN

### Re: 11518 - Dominos 2

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
Impossible says I`m possible

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

### Re: 11518 - Dominos 2

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

vahid sanei
Learning poster
Posts: 84
Joined: Fri Jan 09, 2009 4:37 pm
Location: IRAN

### Re: 11518 - Dominos 2

Thanks Jan
Impossible says I`m possible

tanmoy
New poster
Posts: 18
Joined: Wed Jun 25, 2008 2:25 pm

### Re: 11518 - Dominos 2

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
Learning poster
Posts: 97
Joined: Fri Aug 22, 2008 10:18 pm
Location: CSE.SUST.SYLHET

### Re: 11518 - Dominos 2

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

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

Shafaet_du
Experienced poster
Posts: 147
Joined: Mon Jun 07, 2010 11:43 am
Location: University Of Dhaka,Bangladesh
Contact:

### Re: 11518 - Dominos 2

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

zobayer
Experienced poster
Posts: 110
Joined: Tue May 06, 2008 2:18 pm
Location: CSE-DU, Bangladesh
Contact:

### Re: 11518 - Dominos 2

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.
You should not always say what you know, but you should always know what you say.

receme
New poster
Posts: 17
Joined: Thu Jul 01, 2010 11:55 am

### Re: 11518 - Dominos 2

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
New poster
Posts: 3
Joined: Tue Nov 01, 2011 11:54 am

### Re: 11518 - Dominos 2

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
New poster
Posts: 26
Joined: Fri Oct 28, 2011 2:42 am

### Re: 11518 - Dominos 2

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.
"Learning to love yourself is the greatest love of all" - Michael Masser and Linda Creed

mahade hasan
Learning poster
Posts: 87
Joined: Thu Dec 15, 2011 3:08 pm
Location: University of Rajshahi,Bangladesh

### Re: 11518 - Dominos 2

cutt>>>ACC
Last edited by mahade hasan on Mon Aug 06, 2012 7:54 pm, edited 2 times in total.
we r surrounded by happiness
need eyes to feel it!

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

### Re: 11518 - Dominos 2

If Mat can only be 0 or 1 then make it type bool.
Check input and AC output for thousands of problems on uDebug!

mahade hasan
Learning poster
Posts: 87
Joined: Thu Dec 15, 2011 3:08 pm
Location: University of Rajshahi,Bangladesh

### Re: 11518 - Dominos 2

thanx for ur kind reply
Can You give some I/O?
we r surrounded by happiness
need eyes to feel it!