Page 5 of 6

### Re: 10397 - Connect the Campus

Posted: Fri Jan 25, 2013 5:42 pm
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);
}
}``````

### Re: 10397 - Connect the Campus

Posted: Fri Jan 25, 2013 10:29 pm
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``

### Re: 10397 - Connect the Campus

Posted: Sat Jan 26, 2013 7:25 am

### 10397-Connect the Campus.getting WA

Posted: Fri Jul 05, 2013 5:55 pm
Got Accepted replecing float to double

### Re: 10397-Connect the Campus.getting WA

Posted: Fri Jul 05, 2013 11:04 pm
Try using double instead of float.

### Re: 10397-Connect the Campus.getting WA

Posted: Tue Jul 09, 2013 5:21 pm
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.

### Re: 10397-Connect the Campus.getting WA

Posted: Tue Jul 09, 2013 10:38 pm
It looks like your root function should be returning something.

### Re: 10397-Connect the Campus.getting WA

Posted: Wed Jul 10, 2013 6:28 am
brianfry713 wrote: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 !

### Re: 10397 - Connect the Campus

Posted: Tue Sep 23, 2014 12:06 am
Why do I get a runtime error ?

Code: Select all

``````Acc
``````

### Re: 10397 - Connect the Campus

Posted: Tue Sep 23, 2014 7:15 pm
Try this
Nak wrote: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
rakeb wrote: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

### Re: 10397 - Connect the Campus

Posted: Tue Sep 23, 2014 10:06 pm
TO: lighted

Both tests work, but again Runtime Error.

### Re: 10397 - Connect the Campus

Posted: Tue Sep 23, 2014 11:23 pm
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.

### Re: 10397 - Connect the Campus

Posted: Wed Sep 24, 2014 12:44 am
Thanks, I got Acc by using Scanner.

### Re: 10397 - Connect the Campus

Posted: Sat Jan 24, 2015 2:26 pm
Why Runtime Error??

Code: Select all

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

### Re: 10397 - Connect the Campus

Posted: Tue Jan 27, 2015 10:28 pm
You are probably using too much memory.
Why do you need so many edges?