Page 1 of 11

### 10000 - Longest Paths

Posted: Tue Mar 12, 2002 10:54 pm
This code seems to work whatever I feed it with but I still get WA. Can someone help ?

Code: Select all

``````#include <stdio.h>

int edge;
int node;
int nodes;
int edges, length;

int main()
{
int start, i, j, ncase, cont;

for(scanf("%d",&nodes),ncase=1; nodes>0; scanf("%d",&nodes),ncase++) {
scanf("%d",&start);
edges=-1;
do {
edges++;
scanf("%d %d",&edge[edges],&edge[edges]);
} while (edge[edges] != 0 && edge[edges] != 0);

for(i=1; i<=nodes; i++) node[i]=-1;
node[start]=0;
length=-1;
do {
cont=0;
length++;
for (i=1; i<=nodes; i++)
if (node[i]==length)
for (j=0;j<edges;j++)
if (edge[j]==i) {
node[edge[j]]=length+1;
cont=1;
}
} while (cont);
for (i=1;node[i]<length;i++);

printf("Case %d: The longest path from %d has length %d, finishing at %d.nn",ncase,start,length,i);
}
return 0;
}
``````

Posted: Mon Mar 18, 2002 1:29 pm
Hi!

It is a small bug...
Just increase your table from 5000x2 to
10010x2

And you will get it...

Good Luck ### 10000

Posted: Tue Mar 19, 2002 10:44 pm
#include <iostream.h>
#include <math.h>

struct record
{

record *right;
int y;

};

void calc(record *B[],int start, int &maxl,int &end, int L)
{
if ((L > maxl) || (( L = maxl) && (L > end )) )
{
maxl = L;
end = start;
}

record *q=B[start];
while(q != NULL)
{
calc(B,q->y,maxl,end,L+1);
q = q -> right;
}
}

void delet(record *B[],int number)
{
record *p=B[number],*q;
for(int i = 0; i < number;i++)
{
while(p!= NULL)
{
q = p;
p = p -> right;
delete(q);
}
}
}

void max(record *B[],int x,int y)
{
if(B[x-1] != NULL)
{
record *q = B[x - 1];
while(q-> right != NULL)
{
q = q -> right;
}
record *p = new(record);
q -> right = p;
p -> right = NULL;
p -> y = y - 1;
}
else
{
B[x-1] = new(record);
B[x-1] -> y = y-1;
B[x-1] -> right = NULL;
}
}

void procedure(int number,int cas)
{
int start,maxl=0,end=0;

cin>>start;
start--;
int A;
int j=0;
cin>>A[j];
while(A[j] != 0) //read table a
{
cin>>A[j];
j++;
cin>>A[j];
}
cin>>A[j];
record* B;
for(int i = 0; i< number;i++)
{
B = NULL;
}
int c = 0;
while(A[c] != 0)
{
max(B,A[c],A[c]); // convert from table a to table b
c++;
}

calc(B,start,maxl,end,0); //calculate distacre
cout<<"Case "<<cas<<": The longest path from "<<start+1<<" has length "<<maxl<<", finishing at "<<end + 1<<"."<<endl;
for(int d=0;d<number;d++)
delet(B,d);//delete array from memory
}

void main()
{
int cas=1;
int number;
cin>>number;
while(number != 0)
{
procedure(number,cas);
cin>>number;
cas++;
}

}

Posted: Tue Mar 19, 2002 10:45 pm
it work on my computer, but doesn't work on serwer:((
what could be wrong?

Posted: Tue Mar 19, 2002 11:18 pm
I remember I had a problem with the long line in the output. I splitted it in two parts and got accepted. But I don't know if it is necessary in C++.

Posted: Wed Mar 20, 2002 2:35 am
i tried this way

cout<<"Case ";
cout<<endl;
cout<<cas;
cout<<endl;
cout<<": The longest path from ";
cout<<endl;
cout<<start+1;
cout<<endl;
cout<<" has length ";
cout<<endl;
cout<<maxl;
cout<<endl;
cout<<", finishing at ";
cout<<endl;
cout<<end + 1;
cout<<endl;
cout<<".";
cout<<endl;

and this way, it doesn't work still;

cout<<"Case ";
cout<<cas;
cout<<": The longest path from ";
cout<<start+1;
cout<<" has length ";
cout<<maxl;
cout<<", finishing at ";
cout<<end + 1;
cout<<".";
cout<<endl;

Posted: Wed Mar 20, 2002 2:49 am
Adrian, it's not necessary for C++ to split the line. I'm not sure if there's a limit, but it's definitely way higher than that line. The problem probably was that your mail program splitted the line because it thought it's too long and it splitted it on a wrong position.

Posted: Wed Mar 20, 2002 10:24 am
so what should i do?? to correct this proglem, it gives wrong answer on serwer, but it's working on my computer

Posted: Wed Mar 20, 2002 10:49 am
I think you have made a mistake in procedure calc:
if ((L > maxl) || (( L = maxl) && (L > end )) )
I think you must write L==maxl.
And have you considered this line:
If there are several paths of maximum length, print the final place with smallest number.

Posted: Wed Mar 20, 2002 4:36 pm
this line should be
if ((L > maxl) || (( L == maxl) && (start < end )) )
but it doesn't work still

Posted: Thu Mar 21, 2002 1:35 pm
Are the points numbered from 1 to n?

Posted: Fri Mar 22, 2002 4:54 pm
from 0 to n-1

Posted: Sat Mar 23, 2002 2:58 am
Are you sure? The problem description says "1 to n", and I can't see where you decrease the numbers by one.

Posted: Sat Mar 23, 2002 9:43 am
i do it here void
max(record *B[],int x,int y)
{
if(B[x-1] != NULL)
{
record *q = B[x - 1];
while(q-> right != NULL)
{
q = q -> right;
}
record *p = new(record);
q -> right = p;
p -> right = NULL;
p -> y = y - 1;
}
else
{
B[x-1] = new(record);
B[x-1] -> y = y-1;
B[x-1] -> right = NULL;
}
}

Posted: Sat Mar 23, 2002 10:01 am
#include <iostream.h>
#include <math.h>

struct record
{

record *right;
int y;

};

void calc(record *B[],int start, int &maxl,int &end, int L)
{
if ((L > maxl) || (( L == maxl) && (start < end )) )
{
maxl = L;
end = start;
}

record *q=B[start];
while(q != NULL)
{
calc(B,q->y,maxl,end,L+1);
q = q -> right;
}
}

void delet(record *B[],int number)
{
record *p,*q;
for(int i = 0; i < number;i++)
{
p = B;
while(p != NULL)
{
q = p;
p = p -> right;
delete(q);
}
}
}

void max(record *B[],int x,int y)
{
if(B[x] != NULL)
{
record *q = B[x];
while(q-> right != NULL)
{
q = q -> right;
}
q -> right = new(record);
q = q -> right;
q -> right = NULL;
q -> y = y;
}
else
{
B[x] = new(record);
B[x] -> y = y;
B[x] -> right = NULL;
}
}

void procedure(int number,int cas)
{
int start,maxl=-1,end=-1;

cin>>start;
start--;
int A;
int j=-1;
do
{
j++;
cin>>A[j];
cin>>A[j];
}
while((A[j] != 0) && (A[j] != 0));

record* B;
for(int i = 0; i<= number;i++)
{
B = NULL;
}
int c = 0;
while(A[c] != 0)
{
max(B,A[c]-1,A[c]-1); // convert from table a to table b
c++;
}

calc(B,start,maxl,end,0); //calculate distacre
cout<<"Case "<<cas<<": The longest path from "<<start+1<<" has length "<<maxl<<", finishing at "<<end + 1<<"."<<endl;
// for(int d=0;d<number;d++)
// delet(B,d);//delete array from memory
}

void main()
{
int cas=1;
int number;
cin>>number;
while(number != 0)
{
procedure(number,cas);
cin>>number;
cas++;
}

}

<font size=-1>[ This Message was edited by: PMNOX on 2002-03-23 09:02 ]</font>

<font size=-1>[ This Message was edited by: PMNOX on 2002-03-23 12:38 ]</font>