10147  Highways
Moderator: Board moderators

 Learning poster
 Posts: 83
 Joined: Wed Feb 01, 2006 12:59 pm
 Location: (Fcicu) 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!).
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
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];
#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
i m getting TLE for this problem...can nebody tell me how can i improve the efficiency
here is the code
before using sets, i tried vectors n still got TLE
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=x1x2; dy=y1y2;
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==n1)
break;
}
if(!newh)
cout<<"No new highways need"<<endl;
}
return 0;
}
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.

Rio
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
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
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
Code: Select all
if(hw>=n1)
break;
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
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

 Learning poster
 Posts: 53
 Joined: Sat Jul 29, 2006 7:33 am
 Location: (CSE,DU), Dhaka,Bangladesh
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
Now my question is it correct format just bellow i am indicating?
output
Yes i am trying to say that is it acceptable if the pair format swap just like 3 8 instead of 8 3?
output
Code: Select all
1 6
3 7
4 9
5 7
8 3
output
Code: Select all
1 6
3 7
4 9
5 7
3 8
No venture no gain
with best regards

ishtiaq ahmed
with best regards

ishtiaq ahmed
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.
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.
Who is online
Users browsing this forum: No registered users and 1 guest