10000  Longest Paths
Moderator: Board moderators

 New poster
 Posts: 4
 Joined: Sat Nov 04, 2006 5:40 am
hi ! please show me how did you correct the program
Hi
Im very fresher in this kind of problem and im looking for how I could solve this problem
Please could you post what was wrong with your code?
Regards
Im very fresher in this kind of problem and im looking for how I could solve this problem
Please could you post what was wrong with your code?
Regards
10000 WA. Memory Limit Exceeded!
I've tried every means,and I still got "Memory Limit Exceeded",can anybody help me,please? Thank you.
Code: Select all
#include <stdio.h>
#include <stdlib.h>
struct Edge {
unsigned short int num;
struct Edge *next;
};
struct IN {
unsigned short int n;
int start;
struct Edge **edges;
};
struct node {
unsigned short int num;
unsigned short int depth;
struct node* next;
};
struct result { /* to store the results*/
unsigned short int start;
unsigned short int len;
unsigned short int end;
struct result* next;
};
void freeNode(struct IN *in) {
struct Edge *pt, *et;
unsigned short int i;
for (i = 0; i < in>n; i++) {
pt = (in>edges)[i];
while (pt != NULL) {
et = pt>next;
free(pt);
pt = et;
}
}
free(in>edges);
free(in);
}
void push(struct node **qHead, struct node **qTail, int num, int depth) {
struct node *pt;
pt = malloc(sizeof(struct node));
pt>num = num;
pt>depth = depth;
pt>next = NULL;
if (*qHead == NULL) {
*qHead = pt;
*qTail = pt;
return;
}
(*qTail)>next = pt;
*qTail = pt;
}
struct node* pop(struct node **qHead) {
struct node *pt;
if (*qHead == NULL)
return NULL;
pt = *qHead;
*qHead = (*qHead)>next;
return pt;
}
void process(unsigned short int *len, unsigned short int *end, struct IN *in) {
struct node *qHead, *qTail, *current;
struct Edge *edge;
struct result *rt;
unsigned short int flag;
rt = malloc(sizeof(struct result));
rt>start = in>start;
qHead = NULL;
qTail = NULL;
push(&qHead, &qTail, in>start  1, 0);
*len = 0;
*end = in>n;
while (qHead != NULL) {
current = pop(&qHead);
flag = 1;
for (edge = (in>edges)[current>num]; edge != NULL; edge = edge>next) {
push(&qHead, &qTail, edge>num, current>depth + 1);
flag = 0;
}
if (flag)
if (current>depth > *len) {
*len = current>depth;
*end = current>num;
} else
if (current>depth == *len && current>num < *end)
*end = current>num;
free(current);
}
}
int main() {
struct IN *in;
struct Edge *edge;
int i, j;
struct result *rt, *rtHead, *rtTemp;
rtHead = malloc(sizeof(struct result));
rt = rtHead;
while (1) {
in = malloc(sizeof(struct IN));
scanf("%i", &(in>n));
if (in>n == 0)
break;
in>edges = malloc(sizeof(struct Edge*) * (in>n));
for (i = 0; i < in>n; i++)
(in>edges)[i] = NULL;
scanf("%i", &(in>start));
while (1) {
scanf("%i %i", &i, &j);
if (i == 0 && j == 0) { //process this graph and store the result
process(&(rt>len), &(rt>end), in);
rt>start = in>start;
rt>next = malloc(sizeof(struct result));
rt = rt>next;
freeNode(in);
break;
}
if ((in>edges)[i  1] == NULL) {
(in>edges)[i  1] = malloc(sizeof(struct Edge));
((in>edges)[i  1])>next = NULL;
((in>edges)[i  1])>num = j  1;
} else {
for (edge = (in>edges)[i  1]; edge>next != NULL; edge = edge>next)
;
edge>next = malloc(sizeof(struct Edge));
edge = edge>next;
edge>num = j  1;
edge>next = NULL;
}
/*printf("(in>edges)[%i]>num == %i\n", i  1, j  1);*/
}
}
/*output the results*/
for (rt = rtHead, i = 0; rt>next != NULL;) {
printf("Case %i: The longest path from %i has length %i, finishing at %i.\n",
++i, rt>start, rt>len, rt>end + 1);
rtTemp = rt>next;
free(rt);
rt = rtTemp;
}
free(rt);
return 0;
}
keeping WA
keeping WA (pass all the test cases which i could find on the board)
any idea???
Input:
Output:
thx in advance
any idea???
Code: Select all
Remove after AC, the following test cases are valid.
Code: Select all
2
1
1 2
0 0
5
3
1 2
3 5
3 1
2 4
4 5
0 0
5
5
5 4
5 3
5 2
5 1
4 1
4 2
0 0
8
1
7 1
8 1
1 3
2 3
4 3
3 5
6 2
0 0
6
1
1 2
1 5
2 3
3 4
4 5
5 6
0 0
2
1
1 2
0 0
10
6
1 2
3 4
4 5
5 6
6 7
7 8
8 9
9 10
4 10
7 2
2 8
0 0
2
1
0 0
2
2
0 0
2
2
1 2
0 0
2
1
1 2
0 0
2
1
2 1
0 0
2
2
2 1
0 0
7
1
1 2
1 4
2 7
2 5
4 3
4 6
2 4
3 6
3 7
0 0
0
Code: Select all
Case 1: The longest path from 1 has length 1, finishing at 2.
Case 2: The longest path from 3 has length 4, finishing at 5.
Case 3: The longest path from 5 has length 2, finishing at 1.
Case 4: The longest path from 1 has length 2, finishing at 5.
Case 5: The longest path from 1 has length 5, finishing at 6.
Case 6: The longest path from 1 has length 1, finishing at 2.
Case 7: The longest path from 6 has length 5, finishing at 10.
Case 8: The longest path from 1 has length 0, finishing at 1.
Case 9: The longest path from 2 has length 0, finishing at 2.
Case 10: The longest path from 2 has length 0, finishing at 2.
Case 11: The longest path from 1 has length 1, finishing at 2.
Case 12: The longest path from 1 has length 0, finishing at 1.
Case 13: The longest path from 2 has length 1, finishing at 1.
Case 14: The longest path from 1 has length 4, finishing at 6.
Last edited by sjn on Fri Apr 20, 2007 3:16 am, edited 1 time in total.
Some of your cases are not correct I think. However, here are some cases where your code fails.
Input:
Output:
Hope these help.
Input:
Code: Select all
6
6
6 5
1 4
6 4
5 1
6 1
5 3
5 4
6 2
4 2
0 0
13
11
11 6
13 11
9 1
7 11
4 11
1 12
12 10
12 8
6 9
11 10
6 10
11 8
6 1
5 13
2 13
0 0
0
Code: Select all
Case 1: The longest path from 6 has length 4, finishing at 2.
Case 2: The longest path from 11 has length 5, finishing at 8.
Ami ekhono shopno dekhi...
HomePage
HomePage
I got WA for this problem
I tried many cases and it produces correct output. Does anyone have critical test cases ?
Code: Select all
AC
Last edited by RC's on Wed Aug 15, 2007 6:08 am, edited 1 time in total.

 New poster
 Posts: 21
 Joined: Thu Jun 14, 2007 11:45 pm
I try to use BFS, but I got WA. Can anyone help me?
Thank you.
Code: Select all
AC
Last edited by renato_ferreira on Tue Aug 14, 2007 1:11 am, edited 1 time in total.
Your code is correct, but way to slow. Just generate a set which has 100 nodes and all possible edges. The starting node is 1.
Input:
Output:
Hope it helps.
Input:
Code: Select all
100
1
1 2
1 3
1 4
.
.
.
1 100
2 3
2 4
2 5
.
.
.
2 100
3 4
.
.
.
99 100
0 0
0
Code: Select all
Case 1: The longest path from 1 has length 99, finishing at 100.
Ami ekhono shopno dekhi...
HomePage
HomePage

 New poster
 Posts: 21
 Joined: Thu Jun 14, 2007 11:45 pm
I changed my code, but got WA in 0.189.
Thank you.
Code: Select all
AC
Last edited by renato_ferreira on Tue Aug 14, 2007 1:11 am, edited 1 time in total.

 New poster
 Posts: 21
 Joined: Thu Jun 14, 2007 11:45 pm
I can change the code to work for the inputs, but I get TLE. How can I optimize this code?
Thank you.
Code: Select all
AC
Last edited by renato_ferreira on Tue Aug 14, 2007 1:10 am, edited 1 time in total.