Page 3 of 5
Posted: Sun Mar 12, 2006 1:18 am
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!).

### 10147 Highways - MLE

Posted: Tue Oct 17, 2006 9:21 am
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];

### TLE

Posted: Sat Jun 30, 2007 9:24 pm
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);
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

Posted: Sun Jul 01, 2007 1:49 pm
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

Posted: Sun Jul 01, 2007 9:52 pm
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

### m

Posted: Mon Jul 02, 2007 4:44 am
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

Posted: Mon Jul 02, 2007 5:09 am
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..

Posted: Tue Jul 03, 2007 9:08 am
i m using stl sort...still getting tle....is thr any other algorithm more efficient than kruskal for this problem???

Posted: Tue Jul 03, 2007 9:21 am
Prim. If you implement it carefully, time complexity will be O(n^2) using O(n) memory

----
Rio

Posted: Wed Jul 04, 2007 7:51 pm
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.

Posted: Wed Jul 04, 2007 8:14 pm
helloneo wrote: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???

Posted: Thu Jul 05, 2007 4:55 am
soddy wrote: 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..

Posted: Thu Jul 05, 2007 4:57 am
SARKAR wrote: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..

### Re: 10147 unclear output format

Posted: Thu May 01, 2008 7:27 pm
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?

### Re: 10147 unclear output format

Posted: Fri May 02, 2008 9:27 am
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.