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

Post by vahid sanei »

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 »

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

Post 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
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 »

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

Post by vahid sanei »

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 »

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 »

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 »

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 »

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 »

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 »

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

Post 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.
"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

Post by mahade hasan »

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 »

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

Post by mahade hasan »

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)”