## 10397 - Connect the Campus

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

Moderator: Board moderators

Sabiha_Fancy
New poster
Posts: 24
Joined: Mon Jul 16, 2012 3:43 pm

### Re: 10397 - Connect the Campus

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);
}
}``````
Last edited by brianfry713 on Tue Jan 27, 2015 12:59 am, edited 1 time in total.
Reason: Added code blocks
Fancy

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

### Re: 10397 - Connect the Campus

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``
Check input and AC output for thousands of problems on uDebug!

Sabiha_Fancy
New poster
Posts: 24
Joined: Mon Jul 16, 2012 3:43 pm

### Re: 10397 - Connect the Campus

Thank you for your reply. I got accepted.
Fancy

sun_kuet
New poster
Posts: 12
Joined: Wed Mar 27, 2013 4:28 pm

### 10397-Connect the Campus.getting WA

Got Accepted replecing float to double
Last edited by sun_kuet on Sat Jul 06, 2013 1:58 am, edited 1 time in total.

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

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

Try using double instead of float.
Check input and AC output for thousands of problems on uDebug!

felipe_c
New poster
Posts: 2
Joined: Tue Jul 09, 2013 3:52 pm

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

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.
Last edited by felipe_c on Wed Jul 10, 2013 6:57 am, edited 1 time in total.

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

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

It looks like your root function should be returning something.
Check input and AC output for thousands of problems on uDebug!

felipe_c
New poster
Posts: 2
Joined: Tue Jul 09, 2013 3:52 pm

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

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 !

sreka11
New poster
Posts: 15
Joined: Fri Aug 15, 2014 8:06 pm

### Re: 10397 - Connect the Campus

Why do I get a runtime error ?

Code: Select all

``````Acc
``````
Last edited by sreka11 on Wed Sep 24, 2014 11:27 am, edited 1 time in total.

lighted
Guru
Posts: 587
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

### Re: 10397 - Connect the Campus

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
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

sreka11
New poster
Posts: 15
Joined: Fri Aug 15, 2014 8:06 pm

### Re: 10397 - Connect the Campus

TO: lighted

Both tests work, but again Runtime Error.

lighted
Guru
Posts: 587
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

### Re: 10397 - Connect the Campus

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.
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

sreka11
New poster
Posts: 15
Joined: Fri Aug 15, 2014 8:06 pm

### Re: 10397 - Connect the Campus

Thanks, I got Acc by using Scanner.

ehsanulbigboss
New poster
Posts: 32
Joined: Tue Jul 22, 2014 1:17 am

### Re: 10397 - Connect the Campus

Why Runtime Error??

Code: Select all

``Solved!, I didn't check parent of already connected component while input ``
Last edited by ehsanulbigboss on Wed Jan 28, 2015 9:37 pm, edited 1 time in total.

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

### Re: 10397 - Connect the Campus

You are probably using too much memory.
Why do you need so many edges?
Check input and AC output for thousands of problems on uDebug!