10034 - Freckles

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

Moderator: Board moderators

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

Re: 10034 - Freckles

Post by brianfry713 »

Try Kruskal's algorithm.
Check input and AC output for thousands of problems on uDebug!

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

Re: 10034 - Freckles

Post by brianfry713 »

What if there are >= 100 test cases?

Don't print a blank line at the start of the output.

It doesn't matter the order, so it is easier to print the output right away.

Try to separate the input from the output when you're running the code. You can redirect them to and from files for testing, but the code you submit should read from stdin and write to stdout.
Check input and AC output for thousands of problems on uDebug!

Skynet094
New poster
Posts: 3
Joined: Fri Jul 19, 2013 6:31 pm

Re: 10034 - Freckles

Post by Skynet094 »

Code: Select all

#include<cstdio>
#include<iostream>
#include<map>
#include<cstring>
#include<vector>
#include<cmath>
#include<algorithm>
using namespace std;
#define  x first
#define y second
#define MAX 110

typedef pair<double,double>pii;
pii point[MAX];

int parent[MAX];

struct edge
    {
    int a,b;
    double w;
    bool operator<(const edge &ob) const
    {
    return(w<ob.w);
    }
    }ee;

vector<edge> graph;


int find_ref(int r)
{
    if(parent[r]==r)
        return r;
    else
        return parent[r]=find_ref(parent[r]);
}


double calC(pii a,pii b)
{
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}


double mst(int n)
{
    int count=0;
    double sum=0.0;
    sort(graph.begin(),graph.end());

    for(int i=0;i<graph.size();i++)
    {
        int u_ref=find_ref(graph[i].a);
        int v_ref=find_ref(graph[i].b);
        if(u_ref!=v_ref)
       {
            parent[graph[i].a]=graph[i].b;
            sum+=graph[i].w;
            count++;

            if(count==n-1)
                break;
       }
    }
    return sum;
}


int main(void)
{
//freopen("FILE.txt","w",stdout);
int testcase;
cin>>testcase;

while(testcase--)
{

graph.clear();
memset(parent,0,sizeof(parent));
memset(&ee,0,sizeof(edge));
memset(point,0,sizeof(point));
int n;
cin>>n;  //number of freckles

for(int i=0;i<n;i++)
{   cin>>point[i].x>>point[i].y;   //taking points as input and
    parent[i]=i;                   //creating the set
 }


for(int i=0;i<n-1;i++)  //creating the complete graph here
{
    for(int j=i+1;j<n;j++)
    {
    ee.a=i;
    ee.b=j;
    ee.w=calC(point[i],point[j]);
    graph.push_back(ee);
    //cout<<ee.a.x<<" "<<ee.a.y<<" "<<ee.b.x<<" "<<ee.b.y<<" "<<ee.w<<endl;
    }
}

printf("%0.2lf\n",mst(n));
if(testcase!=0)
    printf("\n");
}

return 0;
}
Help, Passes all the testcases from the forum.Still getting WA.

piotrmizerka
New poster
Posts: 1
Joined: Fri Dec 27, 2013 2:42 pm

Re: 10034 - Freckles

Post by piotrmizerka »

Could anybody with AC give me her/his outs for this data?
Thx in advance!

Code: Select all

100

7
4 0
1 0
3 9
1 9
2 8
5 5
1 5

7
4 2
6 4
2 1
8 4
3 5
6 0
0 0

7
4 4
3 1
2 8
0 8
1 8
5 5
5 0

7
2 6
9 5
3 4
5 5
8 1
9 5
2 8

7
2 4
2 8
1 5
3 7
1 8
2 9
5 4

7
5 5
6 8
3 7
7 7
9 9
6 0
7 6

7
1 0
3 9
7 9
7 2
5 2
8 5
8 3

7
8 9
5 6
3 0
0 7
3 2
3 7
8 7

7
6 1
6 2
8 9
6 0
5 4
8 6
4 8

7
3 1
0 1
7 9
7 8
9 9
1 5
0 4

7
0 6
0 2
0 2
9 5
4 8
6 2
5 8

7
8 1
8 7
1 7
0 1
0 3
5 3
2 2

7
8 1
5 7
3 5
0 3
3 3
7 9
5 2

7
2 7
0 0
2 4
5 4
7 8
3 8
2 8

7
5 4
0 5
8 8
5 7
0 0
4 5
5 6

7
5 5
0 4
5 9
8 2
2 0
8 3
4 1

7
5 2
4 7
4 7
0 3
1 1
1 7
4 9

7
5 8
9 3
5 6
7 3
2 9
4 6
3 3

7
9 7
3 0
7 4
9 9
6 1
8 4
7 2

7
0 3
9 5
0 0
2 1
5 9
5 9
6 9

7
5 3
3 7
5 9
4 9
7 5
3 8
9 0

7
9 8
4 7
6 1
1 9
6 7
4 3
8 6

7
9 6
0 7
6 2
8 2
9 9
8 7
8 7

7
9 6
9 5
0 7
2 7
6 4
4 2
0 1

7
4 8
1 1
1 0
4 0
2 6
3 8
1 2

7
0 0
4 6
3 5
6 9
2 2
0 3
2 2

7
2 1
0 7
4 2
0 1
7 9
9 8
7 1

7
9 5
3 5
3 0
0 3
5 3
0 6
8 6

7
4 8
9 9
1 8
7 8
6 3
5 1
1 7

7
6 2
0 6
2 9
0 2
2 0
1 9
9 0

7
7 7
9 9
5 2
1 4
7 9
9 0
6 2

7
9 5
7 8
2 0
5 2
2 4
9 0
0 4

7
7 1
1 8
7 0
8 5
5 6
5 8
6 1

7
3 7
3 4
2 9
2 6
4 2
4 5
4 2

7
4 0
6 0
5 4
6 8
0 0
3 4
3 2

7
6 7
2 7
9 4
9 4
1 1
8 7
1 7

7
7 1
2 8
8 2
1 5
9 8
9 7
1 6

7
3 3
5 7
3 1
6 0
0 7
9 0
5 7

7
7 0
6 9
6 9
9 1
1 3
0 1
1 7

7
7 3
0 5
7 2
9 8
3 3
6 4
3 2

7
1 8
5 2
5 4
8 4
3 4
4 6
1 7

7
5 0
6 0
0 4
5 9
8 5
8 9
4 9

7
4 1
3 2
0 0
0 5
6 4
6 7
8 1

7
0 3
8 1
5 7
8 0
3 3
2 4
7 5

7
4 3
3 7
0 3
9 1
6 7
2 2
2 6

7
8 0
3 7
8 2
4 4
5 5
5 3
9 4

7
9 7
5 9
6 8
6 9
6 2
9 7
9 3

7
0 1
9 0
1 1
3 6
1 2
3 4
8 0

7
7 4
1 9
8 1
9 9
7 5
9 0
1 0

7
0 3
4 8
0 0
9 5
2 5
2 0
2 0

7
9 8
7 6
6 8
6 9
1 9
0 1
7 5

7
3 4
2 4
5 0
2 4
5 8
6 2
6 5

7
6 6
9 9
1 0
9 7
9 3
3 0
9 5

7
3 0
5 6
5 5
5 1
1 7
1 4
7 3

7
0 4
4 1
5 3
1 5
5 5
9 0
6 8

7
5 6
8 2
8 2
6 7
5 0
3 4
8 7

7
6 8
3 5
2 3
5 7
9 7
0 0
2 0

7
3 9
8 3
0 0
4 9
4 1
1 7
3 2

7
0 3
4 3
7 8
0 1
6 3
6 8
6 9

7
8 8
3 5
8 2
3 3
9 6
7 0
2 3

7
5 0
2 9
6 9
7 2
2 4
8 2
0 0

7
3 6
4 9
2 5
0 3
3 2
0 1
9 1

7
3 5
9 5
2 7
0 7
9 8
9 1
5 7

7
2 0
6 2
3 7
4 0
5 5
1 1
5 1

7
9 9
7 7
6 7
4 6
5 3
4 9
7 6

7
7 1
6 0
2 1
8 3
8 3
4 3
2 8

7
6 7
3 0
0 8
2 2
8 3
3 8
8 4

7
2 7
6 5
5 2
5 7
1 8
5 4
4 9

7
2 6
0 4
7 4
2 8
0 1
7 9
3 4

7
1 5
5 5
2 3
4 6
8 6
4 7
9 3

7
2 8
2 2
3 8
9 1
3 5
7 6
9 0

7
7 6
7 6
4 7
7 2
9 0
2 7
3 7

7
3 3
3 4
1 8
7 5
5 0
8 8
4 6

7
9 8
6 1
8 9
7 1
5 7
3 0
6 0

7
0 4
5 0
0 7
2 5
5 6
5 5
4 9

7
4 8
2 0
5 1
7 0
9 5
3 7
8 2

7
0 0
9 3
1 2
1 4
0 0
5 7
6 9

7
8 5
0 1
0 2
1 8
7 8
3 1
2 9

7
3 7
2 0
3 8
0 8
4 2
4 3
1 6

7
5 1
4 3
5 6
2 0
1 8
5 8
4 5

7
4 6
2 1
1 5
2 1
6 9
0 5
8 2

7
9 5
9 4
1 1
3 5
6 9
0 5
2 6

7
4 4
9 2
4 3
3 7
3 9
3 3
3 7

7
1 7
6 5
5 4
0 7
4 9
7 2
6 7

7
4 5
0 1
4 1
9 6
3 0
0 5
7 9

7
0 6
3 5
0 0
6 8
7 9
2 3
0 9

7
2 8
0 0
3 8
0 9
7 4
1 1
3 9

7
6 3
7 2
7 9
2 6
0 8
9 1
3 6

7
0 3
0 2
5 8
5 2
9 7
3 2
1 5

7
9 3
5 8
1 0
0 0
3 1
2 4
8 6

7
4 1
4 5
9 2
7 3
6 8
6 6
6 5

7
7 5
5 9
1 5
1 3
8 3
2 5
4 6

7
3 0
9 0
3 8
7 1
9 6
0 6
4 1

7
4 4
6 4
5 5
9 7
0 4
0 2
5 4

7
7 9
6 2
9 3
1 4
3 9
3 5
5 5

7
0 5
4 0
4 2
9 7
6 8
2 4
4 6

7
6 4
5 1
9 5
0 2
4 9
9 3
6 7

7
3 3
1 2
4 6
8 9
4 9
2 5
3 8

7
1 6
2 9
8 2
2 4
0 2
5 6
8 5

7
7 7
8 4
9 7
5 2
1 3
0 1
9 3

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

Re: 10034 - Freckles

Post by brianfry713 »

Check input and AC output for thousands of problems on uDebug!

bitaron
New poster
Posts: 12
Joined: Mon Jan 06, 2014 9:40 pm

Re: 10034 - Freckles

Post by bitaron »

I.I got WA no idea why, I really have tried every test case in this forum and all output is correct

Code: Select all

#include<cstdio>
#include<sstream>
#include<cstdlib>
#include<cctype>
#include<cmath>
#include<algorithm>
#include<set>
#include<queue>
#include<stack>
#include<list>
#include<iostream>
#include<fstream>
#include<numeric>
#include<string>
#include<vector>
#include<cstring>
#include<map>
#include<iterator>
#include <fstream>
#include <iomanip>
using namespace std;

struct point
{
	double x,y;
};
struct edge
{
	int s,d;
	double w;
	 bool operator < ( const edge& p ) const { //overloading operator
		 return w > p.w; }
};
vector<point>nodes;
priority_queue<edge>dis;
vector<double>resulted;
int main()
{
	int c,n,i,j,flag[100];
//	vector<int>disflag[100];
	double a,b;
//	vector<double>dis[100];
	vector<int>rnode;
	cin>>c;
	for(i=0;i<c;i++)
	{
		double result=0;
		cout<<"\n";
		cin>>n;
		nodes.clear();
		rnode.clear();
		while(!dis.empty())
		{
			dis.pop();
		}
		for(j=0;j<n;j++)
		{
			cin>>a>>b;
			point temp;
			temp.x=a;
			temp.y=b;
			nodes.push_back(temp);
			flag[j]=0;
		}
		
		int h,k,on=1;
		
		 h=0;
		rnode.push_back(h);
		flag[0]=1;
		while(rnode.size()!=n)
		{
			if(on==1){
			for(k=0;k<n;k++)
			{
				if(flag[k]==0 )
				{
					double t=nodes[h].x-nodes[k].x;
						t=t*t;
					double w=nodes[h].y-nodes[k].y;
						w=w*w;
					double p=t+w;
						p=sqrt(p);
						edge temp;
						temp.s=h;
						temp.d=k;
						temp.w=p;
				//	cout<<"\nrr"<<p<<"  "<<h<<k<<"\n";
						dis.push(temp);
					
						
				}
				
			}
			}
			on=0;
			edge temp2;
			temp2=dis.top();
			dis.pop();
			if(flag[temp2.d]==0)
			{
				rnode.push_back(temp2.d);
				flag[temp2.d]=1;
				result=result+temp2.w;
			//	resulted.push_back(result);
				h=temp2.d;
				on=1;
			}
			
			
		//	cout<<"\nrr"<<result<<"\n";
		}
			//	cout<<"\nrr"<<result<<"\n";
		resulted.push_back(result);
		//cout<<"\n"<<resulted[0]<<"\n";
		
		
	}
for(i=0;i<c;i++)
{
	std::cout << std::fixed;
		std::cout << std::setprecision(2);
		cout<<resulted[i]<<"\n";
}
	return 0;

}

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

Re: 10034 - Freckles

Post by brianfry713 »

Don't print a blank line at the start of the output
Check input and AC output for thousands of problems on uDebug!

bitaron
New poster
Posts: 12
Joined: Mon Jan 06, 2014 9:40 pm

Re: 10034 - Freckles

Post by bitaron »

Sorry for late reply . Tried . But still showing wa.

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

Re: 10034 - Freckles

Post by brianfry713 »

Post your updated code.
Check input and AC output for thousands of problems on uDebug!

bitaron
New poster
Posts: 12
Joined: Mon Jan 06, 2014 9:40 pm

Re: 10034 - Freckles

Post by bitaron »

Code: Select all

#include<cstdio>
#include<sstream>
#include<cstdlib>
#include<cctype>
#include<cmath>
#include<algorithm>
#include<set>
#include<queue>
#include<stack>
#include<list>
#include<iostream>
#include<fstream>
#include<numeric>
#include<string>
#include<vector>
#include<cstring>
#include<map>
#include<iterator>
#include <fstream>
#include <iomanip>
using namespace std;

struct point
{
	double x,y;
};
struct edge
{
	int s,d;
	double w;
	 bool operator < ( const edge& p ) const { //overloading operator
		 return w > p.w; }
};
vector<point>nodes;
priority_queue<edge>dis;
vector<double>resulted;
int main()
{
	int c,n,i,j,flag[10000];
//	vector<int>disflag[100];
	double a,b;
//	vector<double>dis[100];
	vector<int>rnode;
	cin>>c;
	for(i=0;i<c;i++)
	{
		double result=0;
	
		cin>>n;
		nodes.clear();
		rnode.clear();
		while(!dis.empty())
		{
			dis.pop();
		}
		for(j=0;j<n;j++)
		{
			cin>>a>>b;
			point temp;
			temp.x=a;
			temp.y=b;
			nodes.push_back(temp);
			flag[j]=0;
		}
		
		int h,k,on=1;
		
		 h=0;
		rnode.push_back(h);
		flag[0]=1;
		while(rnode.size()!=n)
		{
			if(on==1){
			for(k=0;k<n;k++)
			{
				if(flag[k]==0 )
				{
					double t=nodes[h].x-nodes[k].x;
						t=t*t;
					double w=nodes[h].y-nodes[k].y;
						w=w*w;
					double p=t+w;
						p=sqrt(p);
						edge temp;
						temp.s=h;
						temp.d=k;
						temp.w=p;
				//	cout<<"\nrr"<<p<<"  "<<h<<k<<"\n";
						dis.push(temp);
					
						
				}
				
			}
			}
			on=0;
			edge temp2;
			temp2=dis.top();
			dis.pop();
			if(flag[temp2.d]==0)
			{
				rnode.push_back(temp2.d);
				flag[temp2.d]=1;
				result=result+temp2.w;
			//	resulted.push_back(result);
				h=temp2.d;
				on=1;
			}
			
			
		//	cout<<"\nrr"<<result<<"\n";
		}
			//	cout<<"\nrr"<<result<<"\n";
		resulted.push_back(result);
		//cout<<"\n"<<resulted[0]<<"\n";
		
		
	}
	
	
for(i=0;i<c;i++)
{
	std::cout << std::fixed;
		std::cout << std::setprecision(2);
		cout<<resulted[i]<<"\n";
		
}
	return 0;

}

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

Re: 10034 - Freckles

Post by brianfry713 »

The outputs of two consecutive cases will be separated by a blank line.
Check input and AC output for thousands of problems on uDebug!

bitaron
New poster
Posts: 12
Joined: Mon Jan 06, 2014 9:40 pm

Re: 10034 - Freckles

Post by bitaron »

Did . Bt still wa .

Code: Select all

#include<cstdio>
#include<sstream>
#include<cstdlib>
#include<cctype>
#include<cmath>
#include<algorithm>
#include<set>
#include<queue>
#include<stack>
#include<list>
#include<iostream>
#include<fstream>
#include<numeric>
#include<string>
#include<vector>
#include<cstring>
#include<map>
#include<iterator>
#include <fstream>
#include <iomanip>
using namespace std;

struct point
{
   double x,y;
};
struct edge
{
   int s,d;
   double w;
    bool operator < ( const edge& p ) const { //overloading operator
       return w > p.w; }
};
vector<point>nodes;
priority_queue<edge>dis;
vector<double>resulted;
int main()
{
   int c,n,i,j,flag[10000];
//   vector<int>disflag[100];
   double a,b;
//   vector<double>dis[100];
   vector<int>rnode;
   cin>>c;
   for(i=0;i<c;i++)
   {
      double result=0;
   
      cin>>n;
      nodes.clear();
      rnode.clear();
      while(!dis.empty())
      {
         dis.pop();
      }
      for(j=0;j<n;j++)
      {
         cin>>a>>b;
         point temp;
         temp.x=a;
         temp.y=b;
         nodes.push_back(temp);
         flag[j]=0;
      }
      
      int h,k,on=1;
      
       h=0;
      rnode.push_back(h);
      flag[0]=1;
      while(rnode.size()!=n)
      {
         if(on==1){
         for(k=0;k<n;k++)
         {
            if(flag[k]==0 )
            {
               double t=nodes[h].x-nodes[k].x;
                  t=t*t;
               double w=nodes[h].y-nodes[k].y;
                  w=w*w;
               double p=t+w;
                  p=sqrt(p);
                  edge temp;
                  temp.s=h;
                  temp.d=k;
                  temp.w=p;
            //   cout<<"\nrr"<<p<<"  "<<h<<k<<"\n";
                  dis.push(temp);
               
                  
            }
            
         }
         }
         on=0;
         edge temp2;
         temp2=dis.top();
         dis.pop();
         if(flag[temp2.d]==0)
         {
            rnode.push_back(temp2.d);
            flag[temp2.d]=1;
            result=result+temp2.w;
         //   resulted.push_back(result);
            h=temp2.d;
            on=1;
         }
         
         
      //   cout<<"\nrr"<<result<<"\n";
      }
         //   cout<<"\nrr"<<result<<"\n";
      resulted.push_back(result);
      //cout<<"\n"<<resulted[0]<<"\n";
      
      
   }
   
   
for(i=0;i<c;i++)
{
   std::cout << std::fixed;
      std::cout << std::setprecision(2);
      cout<<resulted[i];
      cout<<"\n";
      cout<<"\n";
      
}
   return 0;

}

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

Re: 10034 - Freckles

Post by brianfry713 »

Don't print an extra blank line at the end of the output.
Check input and AC output for thousands of problems on uDebug!

bitaron
New poster
Posts: 12
Joined: Mon Jan 06, 2014 9:40 pm

Re: 10034 - Freckles

Post by bitaron »

Still WA."For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line. " Dont I need to print the extra blank line ?? I tried omitting both newline one by one . In both cases I got WA.

Code: Select all

#include<cstdio>
#include<sstream>
#include<cstdlib>
#include<cctype>
#include<cmath>
#include<algorithm>
#include<set>
#include<queue>
#include<stack>
#include<list>
#include<iostream>
#include<fstream>
#include<numeric>
#include<string>
#include<vector>
#include<cstring>
#include<map>
#include<iterator>
#include <fstream>
#include <iomanip>
using namespace std;

struct point
{
   double x,y;
};
struct edge
{
   int s,d;
   double w;
    bool operator < ( const edge& p ) const { //overloading operator
       return w > p.w; }
};
vector<point>nodes;
priority_queue<edge>dis;
vector<double>resulted;
int main()
{
   int c,n,i,j,flag[10000];
//   vector<int>disflag[100];
   double a,b;
//   vector<double>dis[100];
   vector<int>rnode;
   cin>>c;
   for(i=0;i<c;i++)
   {
      double result=0;
   
      cin>>n;
      nodes.clear();
      rnode.clear();
      while(!dis.empty())
      {
         dis.pop();
      }
      for(j=0;j<n;j++)
      {
         cin>>a>>b;
         point temp;
         temp.x=a;
         temp.y=b;
         nodes.push_back(temp);
         flag[j]=0;
      }
      
      int h,k,on=1;
      
       h=0;
      rnode.push_back(h);
      flag[0]=1;
      while(rnode.size()!=n)
      {
         if(on==1){
         for(k=0;k<n;k++)
         {
            if(flag[k]==0 )
            {
               double t=nodes[h].x-nodes[k].x;
                  t=t*t;
               double w=nodes[h].y-nodes[k].y;
                  w=w*w;
               double p=t+w;
                  p=sqrt(p);
                  edge temp;
                  temp.s=h;
                  temp.d=k;
                  temp.w=p;
            //   cout<<"\nrr"<<p<<"  "<<h<<k<<"\n";
                  dis.push(temp);
               
                  
            }
            
         }
         }
         on=0;
         edge temp2;
         temp2=dis.top();
         dis.pop();
         if(flag[temp2.d]==0)
         {
            rnode.push_back(temp2.d);
            flag[temp2.d]=1;
            result=result+temp2.w;
         //   resulted.push_back(result);
            h=temp2.d;
            on=1;
         }
         
         
      //   cout<<"\nrr"<<result<<"\n";
      }
         //   cout<<"\nrr"<<result<<"\n";
      resulted.push_back(result);
      //cout<<"\n"<<resulted[0]<<"\n";
      
      
   }
   
   
for(i=0;i<c;i++)
{
   std::cout << std::fixed;
      std::cout << std::setprecision(2);
      cout<<resulted[i];
      cout<<"\n";
   
      
}
   return 0;

}

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

Re: 10034 - Freckles

Post by brianfry713 »

The outputs of two consecutive cases will be separated by a blank line.
For input:

Code: Select all

2

3
1.0 1.0
2.0 2.0
2.0 4.0

3
1.0 1.0
2.0 2.0
2.0 4.0
AC output:

Code: Select all

3.41

3.41
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 100 (10000-10099)”