## 10147 - Highways

Moderator: Board moderators

898989
Learning poster
Posts: 83
Joined: Wed Feb 01, 2006 12:59 pm
Location: (Fci-cu) Egypt
Contact:
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!).

New poster
Posts: 22
Joined: Sun Jan 01, 2006 1:43 pm

### 10147 Highways - MLE

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
New poster
Posts: 23
Joined: Tue May 29, 2007 1:39 am

### TLE

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

rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan
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
New poster
Posts: 23
Joined: Tue May 29, 2007 1:39 am
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
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

### m

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
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea
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
New poster
Posts: 23
Joined: Tue May 29, 2007 1:39 am
i m using stl sort...still getting tle....is thr any other algorithm more efficient than kruskal for this problem???

rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan
Prim. If you implement it carefully, time complexity will be O(n^2) using O(n) memory

----
Rio

SARKAR
New poster
Posts: 21
Joined: Tue May 22, 2007 4:18 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.

soddy
New poster
Posts: 23
Joined: Tue May 29, 2007 1:39 am
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???

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea
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..

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea
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..

ishtiaq ahmed
Learning poster
Posts: 53
Joined: Sat Jul 29, 2006 7:33 am

### Re: 10147 unclear output format

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?
No venture no gain

with best regards
------------------------
ishtiaq ahmed

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

### Re: 10147 unclear output format

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.