10397 - Connect the Campus
Moderator: Board moderators
-
- New poster
- Posts: 27
- Joined: Tue Dec 20, 2005 9:14 am
- Location: Egypt
Re: ACC at last !
I've used O(n^2) for the connections too and got accepted. But I'm not happy with my running time.Sedefcho wrote:Yes, I consider all the connections, it's O(N^2), right. I justCode: Select all
Do you consider every possible connection between the nodes? That's O(n^2)!
use the standard Kruskal's algorithm, that's why I was so
sure I have to get ACC.
How can I improve the part of building the graph (That is, to not consider all possible connections between nodes)? Thanks.
Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.
Are you dreaming right now?
http://www.dreamviews.com
Are you dreaming right now?
http://www.dreamviews.com
-
- New poster
- Posts: 27
- Joined: Tue Dec 20, 2005 9:14 am
- Location: Egypt
Re: 10397 Connect the Campus, WA????
used the union find algorithm.How?? What you have changed in the code?
---
Asmaa Magdi
Asmaa Magdi
RTE
Help..!!
Why RTE ??
code:->
Why RTE ??
code:->
Code: Select all
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<iomanip>
using namespace std;
bool f[1000];
vector<int> v,w;
vector< vector<int> > cn;
void fn(int k){
int i,j,n;
for(i=0;i<cn[k].size();i++){
n=cn[k][i];
if(f[n]){
f[n]=0;
j=0;
while(w[j]!=n) j++;
w.erase(w.begin()+j);
v.push_back(n);
fn(n);
}
}
}
int main(){
int n,m,c[1000][2],i,j,p,p1,p2;
int mn,d;
double ans;
while(cin>>n){
for(i=1;i<=n;i++){
cin>>c[i][0]>>c[i][1];
f[i]=1;
}
cin>>m;
cn.clear();
cn.resize(n+1);
while(m--){
cin>>i>>j;
cn[i].push_back(j);
cn[j].push_back(i);
}
v.clear();w.clear();
v.push_back(1);
for(i=2;i<=n;i++)
w.push_back(i);
f[1]=0;
fn(1);
ans=0.0;
while(w.size()>0){
mn=(c[v[0]][0]-c[w[0]][0])*(c[v[0]][0]-c[w[0]][0])+(c[v[0]][1]-c[w[0]][1])*(c[v[0]][1]-c[w[0]][1]);
p1=v[0];p2=w[0];
p=0;
for(i=0;i<v.size();i++){
for(j=0;j<w.size();j++){
d=(c[v[i]][0]-c[w[j]][0])*(c[v[i]][0]-c[w[j]][0])+(c[v[i]][1]-c[w[j]][1])*(c[v[i]][1]-c[w[j]][1]);
if(d<mn){
mn=d;
p1=v[i];p2=w[j];
p=j;
}
}
}
ans+=sqrt(1.0*mn);
f[w[p]]=0;
fn(p2);
v.push_back(w[p]);
w.erase(w.begin()+p);
}
cout<<setiosflags(ios::fixed)<<setprecision(2)<<ans<<endl;
}
return 0;
}
10397 - Connect the Campus
I get a Runtime Error from UVA and Segmentation Error in another system, probably with the same data tests...
My code checks for array bounds, but I can't seem to understand the failure.
Anyone can see the problem?
Code:
Thanks for all the help. This is my last resort, I've spent quite a few hours looking at it, and testing several inputs.
My code checks for array bounds, but I can't seem to understand the failure.
Anyone can see the problem?
Code:
Code: Select all
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define MAX_V 1000
typedef struct { int v1; int v2; float cost; } edge;
typedef struct point { int x; int y; } point;
edge edges[MAX_V];
point buildings[MAX_V];
int set[MAX_V];
int rank[MAX_V];
int compare (const void * a, const void * b) {
float cost_a = ((edge*) a)->cost, cost_b = ((edge*) b)->cost;
if(cost_a > cost_b) return 1;
else if(cost_a == cost_b) return 0;
else return -1;
}
void link(int a, int b) {
if(rank[a]>rank[b])
set[b]=a;
else {
set[a]=b;
if(rank[a]==rank[b])
rank[b]++;
}
}
int find(int a) {
if(set[a]!=a)
set[a]=find(set[a]);
return set[a];
}
int main (int argc, const char * argv[]) {
//freopen("input.txt", "rb", stdin);
//freopen("output.txt", "wb", stdout);
int num_buildings = -1, num_pipes = -1;
while (scanf("%d%*c", &num_buildings) == 1) {
int num_edges = 0;
for (int i=0; i<num_buildings; i++) {
scanf("%d %d%*c", &buildings[i].x, &buildings[i].y);
set[i]=i;
rank[i]=0;
}
for (int i=0; i<num_buildings; i++) {
for (int k=i+1; k<num_buildings; k++) {
edges[num_edges].v1 = i;
edges[num_edges].v2 = k;
edges[num_edges].cost = sqrt(pow((float) (buildings[i].x-buildings[k].x), 2) + pow((float) (buildings[i].y-buildings[k].y), 2));
num_edges++;
}
}
scanf("%d%*c", &num_pipes);
for (int i = 0, start, end; i<num_pipes; i++) {
scanf("%d %d%*c", &start, &end);
if (start >= 1 && end >= 1)
link(find(start-1), find(end-1));
}
qsort(edges, num_edges, sizeof(edge), compare);
float minCost = 0;
for (int i=0; i<num_edges; i++) {
int v1 = find(edges[i].v1), v2 = find(edges[i].v2);
if (v1 != v2) {
link(v1, v2);
minCost += edges[i].cost;
}
}
printf("%.2f\n", minCost);
}
return 0;
}
Last edited by mrlinx on Sat May 09, 2009 1:26 am, edited 1 time in total.
Re: 10397 - Connect the Campus
Well, you seem to have allocated a very small array for edges:
There's almost 300000 edges in the worst case, not 1000.Code: Select all
#define MAX_V 1000 ... edge edges[MAX_V];
Re: 10397 - Connect the Campus
Hi,
Thanks for catching that. I solved my RE.
Thanks for catching that. I solved my RE.
-
- Learning poster
- Posts: 97
- Joined: Fri Aug 22, 2008 10:18 pm
- Location: CSE.SUST.SYLHET
Re: 10397 - Connect the Campus
Hi some one PLZ help me
i solve 10147 same as this problem
but i got WA in 10397
![]()
![]()
![]()
Code: Select all
CUT after ACC................. :lol: :lol:
Last edited by saiful_sust on Sun Sep 06, 2009 10:53 am, edited 1 time in total.
-
- Learning poster
- Posts: 97
- Joined: Fri Aug 22, 2008 10:18 pm
- Location: CSE.SUST.SYLHET
Re: 10397 - Connect the Campus
Some PLZ help me................![]()
![]()
![]()
-
- Learning poster
- Posts: 97
- Joined: Fri Aug 22, 2008 10:18 pm
- Location: CSE.SUST.SYLHET
Re: 10397 - Connect the Campus
I solve this problem same code as i post here
the problem was double
i change the double type to int then it got acc.......![]()
![]()
But what is wrong with double.?????????
10397 RTE & RTE !!!
Got RTE several times with my code....can any one help me by detecting the reason ....Here is my code...
Code: Select all
#include<iostream>
#include<math.h>
using namespace std;
long n,m,i,j,f,t,p[10000];
double extra;
struct edge
{
long from;
long to;
double dist;
}edg[1000000];
struct node
{
long x;
long y;
}nod[10000];
long parent(long u)
{
if(p[u]==-1) return u;
else
{
p[u]=parent(p[u]);
return p[u];
}
}
int fn(const void *a,const void *b)
{
edge *x=(edge *)a;
edge *y=(edge *)b;
if(x->dist-y->dist>0.00) return 1;
if(x->dist-y->dist>0.00) return -1;
return 0;
}
void FIND_MST()
{
qsort(edg,n*n,sizeof(edg[0]),fn);
for(i=0;i<n*n;i++)
{
if(parent(edg[i].from)!=parent(edg[i].to))
{
extra
+=edg[i].dist;
p[parent(edg[i].from)]=parent(edg[i].to);
}
}
}
int main()
{
double aa,aaa;
while(scanf("%ld",&n)!=EOF)
{
for(i=0;i<n;i++)
{
p[i]=-1;
cin>>f>>t;
nod[i].x=f+10000;
nod[i].y=t+10000;
}
cin>>m;
for(i=0;i<m;i++)
{
cin>>f>>t;
edg[(f-1)*n+t-1].from=f-1;
edg[(f-1)*n+t-1].to=t-1;
p[parent(edg[(f-1)*n+t-1].from)]=parent(edg[(f-1)*n+t-1].to);
}
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
edg[(i*n)+j].from=i;
edg[(i*n)+j].to=j;
if(i==j)
{
edg[(i*n)+j].dist=0.00;
}
else
{
edg[(i*n)+j].dist=sqrt((nod[i].x-nod[j].x)*(nod[i].x-nod[j].x)+(nod[i].y-nod[j].y)*(nod[i].y-nod[j].y));
}
}
}
extra=0.00;
FIND_MST();
printf("%.2lf\n",extra);
}
return 0;
}