10147 - Highways

[898989]

Salamo Aleko
I got accepted in both problems with exactly the same code
May be some think wrong logically in your code.Check it or upload it
and i may help....But put in mind.10379 is more easier in the input
so you can get ac easily but 10147 has large inputs and hard to get within time.
I have implemented Kruskal's algorithm using union set (including union by rank and path compression!).

[taskin]

this is saying MLE, which should not be. can anyone help me? here fx & fy r local & other 2 r global.

#define SIZE 751

struct Edge {
int u, v;
double w;
bool is_MST;
};

struct Node {
int size;
int father;
};

Node forest[SIZE];
Edge A[SIZE * SIZE];
double fx[SIZE],fy[SIZE];

[soddy]

i m getting TLE for this problem...can nebody tell me how can i improve the efficiency
here is the code

Code: Select all

#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<set>
using namespace std;
struct edges{
	int v1,v2;
	int w;
};	
struct point{
	int x,y;
};	
bool compare(const edges& e1,const edges& e2)
{
	return e1.w<e2.w;
}	
int find_set(int v,vector< set<int> >vset)
{
	for(int i=0;i<vset.size();i++)
	{
		set<int>::iterator p;
		p = vset[i].find(v);
		if(p != vset[i].end())
			return i;
	}
	return -1;
}	
int dist(int x1,int y1,int x2,int y2)
{
	int d,dx,dy;
	dx=x1-x2; dy=y1-y2;
	d=(dx*dx)+(dy*dy);
	return d;
}	
int main()
{
	int kases;
	cin>>kases;
	bool first=true;
	while(kases--)
	{
		if(!first)
			cout<<endl;
		first=false;	
		int n;
		cin>>n;
		vector< set<int> > vset(n);
		for(int i=0;i<n;i++)
		{
			set<int> s;
			s.insert(i);
			vset[i]=s;
		}	
		vector<edges> E;
		vector<point> P;
		edges e;
		point p;
		for(int i=0;i<n;i++)
		{
			cin>>p.x>>p.y;
			for(int j=0;j<P.size();j++)
			{
				int w=dist(P[j].x,P[j].y,p.x,p.y);
				e.v1=j; e.v2=i; e.w=w;
				E.push_back(e);
			}
			P.push_back(p);
		}
		sort(E.begin(),E.end(),&compare);
		//Already built highways
		int m,hw=0;
		cin>>m;
		for(int i=0;i<m;i++)
		{
			int x,y;
			cin>>x>>y;
			x--; y--;
			if(x!=y)
			{
				int mn=min(x,y),mx=max(x,y);
				vset[mn].insert(vset[mx].begin(),vset[mx].end());
				vset[mx].clear();
				hw++;
			}	
		}
		//New highways to be built
		bool newh=false;
		for(int i=0;i<E.size();i++)
		{
			int x=find_set(E[i].v1,vset);
			int y=find_set(E[i].v2,vset);
			if(x!=y)
			{
				newh=true;
				cout<<E[i].v1+1<<" "<<E[i].v2+1<<endl;
				int mn=min(x,y),mx=max(x,y);
				vset[mn].insert(vset[mx].begin(),vset[mx].end());
				vset[mx].clear();
				hw++;
			}	
			if(hw==n-1)
				break;
		}
		if(!newh)
			cout<<"No new highways need"<<endl;
	}
	return 0;
}	

before using sets, i tried vectors n still got TLE

[rio]

I'm not good at C++, so I can't understand your code well.
Could you give a brief explanation of your algorithm ?

Anyway, heres a test case which your code doesn't work.

Code: Select all

1

4
0 0
0 1
1 1
1 0
4
1 2
1 3
2 4
3 4

----
Rio

[soddy]

i can take care of ur case....actually i needed to chk dis at the beginning of the loop but i chked at the end

Code: Select all

if(hw>=n-1)
        break; 

I m implementing Kruskal algorithm....i implemented Kruskal in the same way for 908 and 10034 and got AC in 0.00 and 0.123 repectively.......maybe this code demands a lot more efficiency so i m getting TLE

[rio]

I don't feel Kruskal feasible for this problem, as you must to generate all n*(n+1)/2 edges.

In problem 908, edges in all given, so Kruskal is feasible for this (I also used Kruskal for this problem).
Though Problem 10034 is metric MST as this problem is , its upper limit is 100.

----
Rio

[helloneo]

I got AC with Kruskal..
But it's so slow..
9.937 sec with qsort() library in C
and 3.064 sec with my own quick sort..

[soddy]

i m using stl sort...still getting tle....is thr any other algorithm more efficient than kruskal for this problem???

[rio]

Prim. If you implement it carefully, time complexity will be O(n^2) using O(n) memory

----
Rio

[SARKAR]

i used kruskal.
finding all edges and sorting them is o(n^2log(n^2)) task



i used stl library for sorting
can this be done more effeciantely.

[soddy]

I got AC with Kruskal..
But it's so slow..
9.937 sec with qsort() library in C
and 3.064 sec with my own quick sort..

i always thought stl is very efficient....can we code our own function three times efficient than stl ones???

[helloneo]

i always thought stl is very efficient....can we code our own function three times efficient than stl ones???

STL is slow even though it guarantees the time complexity..
If we make our code with the same time complexity, it will be much faster..

[helloneo]

i used kruskal.
finding all edges and sorting them is o(n^2log(n^2)) task



i used stl library for sorting
can this be done more effeciantely.

Try not to use STL.. like vector, set, sort
If you still get TLE, try Prim's algorithm like rio said..

[ishtiaq ahmed]

I have a problem with the output format. According to the sample inputs the outputs are given such like this
output

Code: Select all

1 6
3 7
4 9
5 7
8 3

Now my question is it correct format just bellow i am indicating?
output

Code: Select all

1 6
3 7
4 9
5 7
3 8

Yes i am trying to say that is it acceptable if the pair format swap just like 3 8 instead of 8 3?

[sohel]

This problem has a special judge - that means there are multiple outputs and any correct one will be accepted.
The output format isn't mentioned in the problem statement and thus you are free to choose your own way.
{8 3} and {3 8} are equivalent.