10000 - Longest Paths

Ioura · Post by **Ioura** » 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 ?

#include <stdio.h>

int edge[5000][2];
int node[101];
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][0],&edge[edges][1]);
        } while (edge[edges][0] != 0 && edge[edges][1] != 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][0]==i) {
                            node[edge[j][1]]=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;
}

cyfra · Post by **cyfra** » 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

PMNOX · Post by **PMNOX** » 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[101][2];
int j=0;
cin>>A[j][0];
while(A[j][0] != 0) //read table a
{
cin>>A[j][1];
j++;
cin>>A[j][0];
}
cin>>A[j][1];
record* B[101];
for(int i = 0; i< number;i++)
{
B = NULL;
}
int c = 0;
while(A[c][0] != 0)
{
max(B,A[c][0],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++;
}

}

PMNOX · Post by **PMNOX** » Tue Mar 19, 2002 10:45 pm

it work on my computer, but doesn't work on serwer:((
what could be wrong?

Adrian Kuegel · Post by **Adrian Kuegel** » 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++.

PMNOX · Post by **PMNOX** » 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;

Stefan Pochmann · Post by **Stefan Pochmann** » 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.

PMNOX · Post by **PMNOX** » 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

Adrian Kuegel · Post by **Adrian Kuegel** » 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.

PMNOX · Post by **PMNOX** » Wed Mar 20, 2002 4:36 pm

this line should be
if ((L > maxl) || (( L == maxl) && (start < end )) )
but it doesn't work still

junjieliang · Post by **junjieliang** » Thu Mar 21, 2002 1:35 pm

Are the points numbered from 1 to n?

PMNOX · Post by **PMNOX** » Fri Mar 22, 2002 4:54 pm

from 0 to n-1

Stefan Pochmann · Post by **Stefan Pochmann** » 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.

PMNOX · Post by **PMNOX** » 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;
}
}

PMNOX · Post by **PMNOX** » 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[101][2];
int j=-1;
do
{
j++;
cin>>A[j][0];
cin>>A[j][1];
}
while((A[j][0] != 0) && (A[j][1] != 0));

record* B[101];
for(int i = 0; i<= number;i++)
{
B = NULL;
}
int c = 0;
while(A[c][0] != 0)
{
max(B,A[c][0]-1,A[c][1]-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>