10959 - The Party, Part I

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

Moderator: Board moderators

renato_ferreira
New poster
Posts: 21
Joined: Thu Jun 14, 2007 11:45 pm

Post by renato_ferreira » Tue Jul 17, 2007 6:39 pm

Hello, I don't know why I'm getting WA... My algotithm:

1 - Make a graph with no edges.
2 - Read the input of the dances and make the edges.
3 - Find the Shortest Path from the vertex 0 for all other vertices.

Is that correct? Thank you.

ayeshapakhi
Learning poster
Posts: 60
Joined: Sun Apr 16, 2006 7:59 pm

Post by ayeshapakhi » Wed Jul 18, 2007 12:14 am

Initilize the matrix grafo with 0 everytime u take input..

Code: Select all

while (casos--){
       //
      //        
      scanf("%d %d", &pessoas, &pares); 
      // initialize grafo here
}

renato_ferreira
New poster
Posts: 21
Joined: Thu Jun 14, 2007 11:45 pm

Post by renato_ferreira » Wed Jul 18, 2007 12:19 am

Thank you very much! I got AC! :D :D

sazzadcsedu
Experienced poster
Posts: 136
Joined: Sat Nov 29, 2008 8:01 am
Location: narayangong,bangladesh.
Contact:

10959 - The Party, Part I

Post by sazzadcsedu » Fri Feb 27, 2009 10:53 pm

Code: Select all

deleted,after ACC.	
Life is more complicated than algorithm.
http://felix-halim.net/uva/hunting.php?id=32359
For Hints: http://salimsazzad.wordpress.com

karo9
New poster
Posts: 1
Joined: Thu Jan 21, 2010 11:19 pm

Re: 10959 - The Party, Part I

Post by karo9 » Thu Jan 21, 2010 11:23 pm

Hi
Can someone help me with this task. I've tried different implementation of bfs but none worked:( here is example :

Code: Select all

#include <cstdio>
#include <vector>
#include <queue>

std::vector<int> a[1009];
std::queue<int> Q;
int D[1009];
bool color[1009];

void Bfs(int s)
{
	int u, v;
	color[s] = true;
	D[s] = 0;
	Q.push(s);
	while(!Q.empty())
	{
		u = Q.front();
		Q.pop();
		for(int i = 0; i < a[u].size(); ++i)
		{
			v = a[u][i];
			if(!color[v])
			{
				color[v] = true;
				D[v] = D[u]+1;
				Q.push(v);
			}
		}
	}
}

int main()
{
	int t;
	scanf("%d", &t);
	//getchar();
	//getchar();
	for(int i = 0; i < t; ++i)
	{
		int n, m;
		scanf("%d %d", &n, &m);
		for(int j = 0; j < n; ++j)
		{
			color[j] = false;
			D[j] = 0;
			a[j].clear();
		}
		int u, v;
		for(int j = 0; j < m; ++j)
		{
			scanf("%d %d", &u, &v);
			a[u].push_back(v);
			a[v].push_back(u);
		}
		Bfs(0);
		for(int j = 1; j < n; ++j)
			printf("%d\n", D[j]);
		printf("\n");
	}
	return 0;
}

WA :(

DD
Experienced poster
Posts: 145
Joined: Thu Aug 14, 2003 8:42 am
Location: Mountain View, California
Contact:

Re: 10959 - The Party, Part I

Post by DD » Wed Mar 30, 2011 6:19 am

karo9 wrote:Hi
Can someone help me with this task. I've tried different implementation of bfs but none worked:( here is example :

Code: Select all

#include <cstdio>
#include <vector>
#include <queue>

std::vector<int> a[1009];
std::queue<int> Q;
int D[1009];
bool color[1009];

void Bfs(int s)
{
	int u, v;
	color[s] = true;
	D[s] = 0;
	Q.push(s);
	while(!Q.empty())
	{
		u = Q.front();
		Q.pop();
		for(int i = 0; i < a[u].size(); ++i)
		{
			v = a[u][i];
			if(!color[v])
			{
				color[v] = true;
				D[v] = D[u]+1;
				Q.push(v);
			}
		}
	}
}

int main()
{
	int t;
	scanf("%d", &t);
	//getchar();
	//getchar();
	for(int i = 0; i < t; ++i)
	{
		int n, m;
		scanf("%d %d", &n, &m);
		for(int j = 0; j < n; ++j)
		{
			color[j] = false;
			D[j] = 0;
			a[j].clear();
		}
		int u, v;
		for(int j = 0; j < m; ++j)
		{
			scanf("%d %d", &u, &v);
			a[u].push_back(v);
			a[v].push_back(u);
		}
		Bfs(0);
		for(int j = 1; j < n; ++j)
			printf("%d\n", D[j]);
		printf("\n");
	}
	return 0;
}

WA :(
There is a extra line at the end of your output. You should only print a blank line between two cases.
Have you ever...
  • Wanted to work at best companies?
  • Struggled with interview problems that could be solved in 15 minutes?
  • Wished you could study real-world problems?
If so, you need to read Elements of Programming Interviews.

Top Secret
New poster
Posts: 5
Joined: Tue Mar 12, 2013 12:31 am

Re: 10959 - The Party, Part I

Post by Top Secret » Tue Mar 12, 2013 12:36 am

:cry: :cry: :cry: :cry: :cry: :cry: :cry: :cry:

i think my fault is in presentation.. I used BFS... Plz help me... :cry: :cry: :cry: :cry:

Code: Select all


Got AC!!! Yaeeeeeee!!

While(1) Return Thanks! :D


Last edited by Top Secret on Tue Mar 12, 2013 10:49 pm, edited 2 times in total.

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

Re: 10959 - The Party, Part I

Post by brianfry713 » Tue Mar 12, 2013 10:49 pm

The outputs of two consecutive cases will be separated by a blank line. Don't print a blank line after the last test case.
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 109 (10900-10999)”