10397 - Connect the Campus

[Sabiha_Fancy]

Getting wrong answer for this problem. If any one help to find out the error i will be glad .

Code: Select all

#include<stdio.h>
#include<math.h>

void cloud(int oldvalue,int newvalue,int N);
double distance(int x1,int x2,int y1,int y2);
void heapsort(long int count);
void Build_Max_Heap(long int count);
void Max_Heapify(long int i,long int count);

struct node {
	int x;
	int y;
	int cloud;
	int id;
}V[760];

struct edge {
	struct node v1;
	struct node v2;
	double dist;
}E[577600];

int main()
{
	int N,i,edge,v1,v2,j,temp,caz;
	long int count;
	double sum;
	while(scanf("%d",&N)==1)
	{
		for(i=1; i<=N; ++i)
		{
			scanf("%d %d",&V[i].x,&V[i].y);
			V[i].cloud = i;
			V[i].id = i;
		}
		scanf("%d",&edge);
		for(i=1; i<=edge; ++i)
		{
			scanf("%d %d",&v1,&v2);
			cloud(v2,v1,N);
		}
		count = 0;
		for(i=1; i<N; ++i)
		{
			for(j=i+1; j<=N; ++j)
			{
				if(V[i].cloud != V[j].cloud)
				{
					count++;
					E[count].v1 = V[i];
					E[count].v2 = V[j];
					E[count].dist = distance(V[i].x,V[j].x,V[i].y,V[j].y);
				}
			}
		}
		heapsort(count);
		temp = 0;
		caz = N - 1 - edge;
		j = 1;
		sum = 0.0;
		while(temp < caz)
		{
			if(V[E[j].v1.id].cloud != V[E[j].v2.id].cloud)
			{
				sum += E[j].dist;
				cloud(V[E[j].v2.id].cloud,V[E[j].v1.id].cloud,N);
				temp++;
			}
			j++;
		}
		printf("%.2lf\n",sum);
	}
	return 0;
}

void cloud(int oldvalue,int newvalue,int N)
{
	int i;
	for(i=1; i<=N; ++i)
	{
		if(V[i].cloud == oldvalue)
			V[i].cloud = newvalue;
	}
}

double distance(int x1,int x2,int y1,int y2)
{
	int x,y,dis1;
	double dis2;
	x = x1-x2;
	y = y1-y2;
	dis1 = (x*x) + (y*y);
	dis2 = dis1*1.0;
	return sqrt(dis2);
}

void Build_Max_Heap(long int count)
{
	long int i;
	for(i=floor(count/2); i>0; --i)
		Max_Heapify(i,count);
}

void Max_Heapify(long int i,long int count)
{
	long int L,R,largest;
	struct edge test;
	L = 2*i;
	R = 2*i + 1;
	if(L<=count && E[L].dist>E[i].dist)
	{
		largest = L;
	}
	else
		largest = i;
	if(R<=count && E[R].dist>E[largest].dist)
		largest = R;
	if(largest != i)
	{
		test = E[i];
		E[i] = E[largest];
		E[largest] = test;
		Max_Heapify(largest,count);
	}
}

void heapsort(long int count)
{
	long int i,c;
	struct edge test;
	c = count;
	Build_Max_Heap(count);
	for(i=c; i>1; --i)
	{
		test = E[i];
		E[i] = E[1];
		E[1] = test;
		c--;
		Max_Heapify(1,c);
	}
}

[brianfry713]

Input:

Code: Select all

4
103 104
104 100
104 103
100 100
3
1 2
1 3
2 3

Correct output:

Code: Select all

4.00

[Sabiha_Fancy]

Thank you for your reply. I got accepted.

[sun_kuet]

Got Accepted replecing float to double

[brianfry713]

Try using double instead of float.

[felipe_c]

I'm getting WA too...
The variables name are in portuguese ... but i've made some comments in english
I dont know what is wrong in this code ! And for me it's impossible to skip to another without solving it
For every input that my program receives (until now ) it gives the right answer.

Please ! Someone help me.

[brianfry713]

It looks like your root function should be returning something.

[felipe_c]

It looks like your root function should be returning something.

Dude, I CAN'T BELIEVE THISSS !!!!

I can't believe that I missed it.
I can't believe that a compiler (DEVil C++)doesn't remind me that a function must return a value !(Even with debug)
I'm on this code since june 21 !

I just ..... love you Brian !

[sreka11]

Why do I get a runtime error ?

Code: Select all

Acc

[lighted]

Try this

Did you consider a disconnected input graph?

Input:

4
0 0
0 1
1 0
1 1
2
1 2
3 4

Output should be 1.00

i am not too sure about ur MST algorithm, i think it's better you use kruskal or prim. i assigned cost 0.0 for the existing cables and used kruskal.

[cpp]
scanf("%ld",&nc);
while(nc--)
{
scanf("%ld%ld",&i,&j);
m[j]=0.0;
}
[/cpp]

INPUT:
6
0 0
200 50
100 200
50 300
300 200
300 300
2
3 4
5 6

6
0 0
200 50
100 200
50 300
300 200
300 300
5
1 2
2 3
3 4
4 5
5 6

OUTPUT:
566.71
0.00

[sreka11]

TO: lighted

Both tests work, but again Runtime Error.

[lighted]

I posted that tests because it shows RE here. http://ideone.com/9cxlbN
I am not sure if it is main reason of RE, but when you seperate any input tests by a blank line it gives RE.

[sreka11]

Thanks, I got Acc by using Scanner.

[ehsanulbigboss]

Why Runtime Error??

Code: Select all

Solved!, I didn't check parent of already connected component while input 

[brianfry713]

You are probably using too much memory.
Why do you need so many edges?