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

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

11518 - Dominos 2

Post by vahid sanei » Fri Mar 06, 2009 12:53 pm

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

Post by Jan » Fri Mar 06, 2009 8:21 pm

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

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

Re: 11518 - Dominos 2

Post by vahid sanei » Sat Mar 07, 2009 6:35 am

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

Post by Jan » Sat Mar 07, 2009 6:51 am

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

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

Re: 11518 - Dominos 2

Post by vahid sanei » Sat Mar 07, 2009 7:00 am

Thanks Jan :D
Impossible says I`m possible

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

Re: 11518 - Dominos 2

Post by tanmoy » Sat Apr 04, 2009 5:53 pm

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

Post by saiful_sust » Sun Oct 10, 2010 5:01 pm

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

Check ur bool map array !!!!!!!!!!! :D :D :D
  • 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

Post by Shafaet_du » Wed Oct 20, 2010 9:50 am

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

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

Re: 11518 - Dominos 2

Post by zobayer » Wed Nov 03, 2010 9:11 pm

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

Post by receme » Sat Jan 22, 2011 7:56 pm

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

Post by marjan » Thu Nov 03, 2011 11:18 am

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.

User avatar
outsbook
New poster
Posts: 26
Joined: Fri Oct 28, 2011 2:42 am

Re: 11518 - Dominos 2

Post by outsbook » Mon Nov 21, 2011 5:34 pm

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

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

Re: 11518 - Dominos 2

Post by mahade hasan » Thu May 17, 2012 9:49 pm

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

Post by brianfry713 » Fri May 18, 2012 12:23 am

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

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

Re: 11518 - Dominos 2

Post by mahade hasan » Fri May 18, 2012 7:28 pm

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

Post Reply

Return to “Volume 115 (11500-11599)”