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

Post by Sabiha_Fancy » 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);
	}
}
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

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

Post by Sabiha_Fancy » Sat Jan 26, 2013 7:25 am

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

Post by sun_kuet » Fri Jul 05, 2013 5:55 pm

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

Post by brianfry713 » Fri Jul 05, 2013 11:04 pm

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

Post by felipe_c » 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 :cry: :cry:
For every input that my program receives (until now :D ) 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

Post by brianfry713 » Tue Jul 09, 2013 10:38 pm

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

Post by felipe_c » 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 :evil: 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

Post by sreka11 » Tue Sep 23, 2014 12:06 am

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: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

Re: 10397 - Connect the Campus

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

Post by sreka11 » Tue Sep 23, 2014 10:06 pm

TO: lighted

Both tests work, but again Runtime Error.

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

Re: 10397 - Connect the Campus

Post by lighted » 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.
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

Post by sreka11 » Wed Sep 24, 2014 12:44 am

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

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

Post by brianfry713 » Tue Jan 27, 2015 10:28 pm

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!

Post Reply

Return to “Volume 103 (10300-10399)”