10034 - Freckles

[brianfry713]

Try Kruskal's algorithm.

[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.

[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]

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]

http://www.uvatoolkit.com/problemssolve.php

[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]

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

[bitaron]

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

[brianfry713]

Post your updated code.

[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]

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

[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]

Don't print an extra blank line at the end of the output.

[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]

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