## 10308 - Roads in the North

Moderator: Board moderators

daveon
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 am
I guess the input contains empty villages.

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea
daveon wrote:I guess the input contains empty villages.
I guess so but what I meant is the first blank is seperator, and the second is input, the third is seperator and what is the 4th ..?

daveon
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 am
I agree, three empty lines would make a lot more sense. But I suppose an empty village takes up two lines.

nymo
Experienced poster
Posts: 149
Joined: Sun Jun 01, 2003 8:58 am
Location: :)
I get ACC assuming 3 empty lines for the above test case.
regards,
nymo

daveon
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 am
There must be something fishy about the io for this problem. Hmmm...

ral
New poster
Posts: 5
Joined: Tue Jan 09, 2007 12:06 am

### 10308 - Roads in the North - WA

I'm getting WA but i don't know why.
Does anyone can help me with this problem?

My code:

Code: Select all

``````#include <stdio.h>
#include <stdlib.h>
#define MAX_BUFF 1000
#define MAX 10000

struct Aresta {
int o;
int d;
int t;
} a[MAX];

int pos[MAX];

int compare (struct Aresta *a, struct Aresta *b)
{
if(a -> o == b -> o)
return a -> d - b -> d;
return a -> o - b -> o;
}

int Best (int x, int pai, int *best)
{
int i;
int num, max1 = 0, max2 = 0;
for(i = pos[x]; ; i++) {
if(a[i].o != x)
break;
if(a[i].d != pai) {
/*printf("Best(%d, %d, %d)\n", a[i].d, x, *best);*/
num = a[i].t + Best(a[i].d, x, best);
/*printf("num = %d\n", num);*/
if(num > max1) {
max2 = max1;
max1 = num;
}
else if(num > max2)
max2 = num;
}
}
/*printf("%d: %d %d\n", x, max1, max2);*/
if(max1 + max2 > *best)
*best = max1 + max2;
return max1;
}

int main ()
{
char c;
char buff[MAX_BUFF];
int count;
int i;
int best;
int no1, no2, distancia;
while(scanf("%c", &c) == 1) {
if(c == '\n') {
printf("0\n");
scanf("%*c");
continue;
}
ungetc(c, stdin);
count = 0;
while(fgets(buff, MAX, stdin) && buff[0] != '\n') {
sscanf(buff, "%d %d %d", &no1, &no2, &distancia);
a[count].o = a[count + 1].d = no1;
a[count].d = a[count + 1].o = no2;
a[count].t = a[count + 1].t = distancia;
count += 2;
}
if(count > 0) {
qsort(a, count, sizeof(struct Aresta), compare);
for(i = 0; i < count; i++)
if(i == 0 || a[i - 1].o != a[i].o)
pos[a[i].o] = i;
else
pos[a[i].o] = pos[a[i - 1].o];
best = 0;
if(count == 2)
best = 0;
else
Best(a[0].o, -1, &best);
printf("%d\n", best);
}
else
printf("0\n");
}
return 0;
}
``````
Rodrigo Alves Lima
Brazil

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea
Finally got AC..~!
My program failed on this case..

Code: Select all

``````1 2 3
2 3 3
3 4 3
``````

suneast
New poster
Posts: 49
Joined: Sun Jan 17, 2010 6:25 am
Location: FZU
Contact:

### Re: 10308 - Roads in the North

faint
I think the judge's data have changed....

Code: Select all

``````5 1 6
1 4 5
6 3 9
2 6 8
6 1 7

5 1 6
1 4 5
6 3 9
2 6 8
6 1 7
``````
and the output should be

Code: Select all

``````22
0
0
0
22
``````
hope I am help to you all

SyFy
New poster
Posts: 13
Joined: Tue Jun 19, 2012 12:16 pm
Contact:

### Re: 10308 - Roads in the North

My AC program gives another output :

Code: Select all

``````22
0
0
22
``````
suneast wrote:faint
I think the judge's data have changed....

Code: Select all

``````5 1 6
1 4 5
6 3 9
2 6 8
6 1 7

5 1 6
1 4 5
6 3 9
2 6 8
6 1 7
``````
and the output should be

Code: Select all

``````22
0
0
0
22
``````
hope I am help to you all

Mukit Chowdhury
Learning poster
Posts: 98
Joined: Fri Aug 17, 2012 9:23 pm
Location: Dhaka
Contact:

### Re: 10308 - Roads in the North

Code: Select all

``````The problem statement is wrong.... This problem says "The area has up to 10,000 villages connected by road segments. The villages are numbered from 1. "-doesn't it mean that,nodes are numbered from 1 ?? That means the villages are numbered from 1,2,3,4,5,....,n.But I got WA thinking this.... the minimum & maximum node can be any number...but there difference will be always one... After coding in this way,I made this problem Accepted... :)
``````

?????? ????
New poster
Posts: 7
Joined: Tue Apr 03, 2012 2:34 pm

### Re: 10308 - Roads in the North

Code: Select all

``````Remove After Accepted
``````

DD
Experienced poster
Posts: 145
Joined: Thu Aug 14, 2003 8:42 am
Location: Mountain View, California
Contact:

### Re:

daveon wrote:INPUT:

Code: Select all

``````5 1 6
1 4 5
6 3 9
2 6 8
6 1 7
(blank line)
(blank line)
(blank line)
(blank line)
5 1 6
1 4 5
6 3 9
2 6 8
6 1 7
``````
OUTPUT:

Code: Select all

``````22
0
22
``````
I think there is one extra line in your sample input. You probably may want to remove it.
Have you ever...
• Wanted to work at best companies?
• Struggled with interview problems that could be solved in 15 minutes?
• Wished you could study real-world problems?
If so, you need to read Elements of Programming Interviews.

Top Secret
New poster
Posts: 5
Joined: Tue Mar 12, 2013 12:31 am

### Re: 10308 - Roads in the North

MY CODE ALSO WORKS FOR THE BLANK LINES... NOW WHAT?????

Code: Select all

``````while(1) return Thanks..
``````
Last edited by Top Secret on Tue Mar 12, 2013 10:47 pm, edited 1 time in total.

lbv
Experienced poster
Posts: 128
Joined: Tue Nov 29, 2011 8:40 am

### Re: 10308 - Roads in the North

Top Secret wrote: MY CODE ALSO WORKS FOR THE BLANK LINES... NOW WHAT?????/
Hi,

Did you test the code you posted? It doesn't print anything for any test case you feed it.

Notice that EOF is a macro defined in the standard headers, and it typically is defined as the constant (-1). This means that this:

Code: Select all

``````while(!EOF)
``````
Translates into:

Code: Select all

``````while(!(-1))
``````
Which always evaluates to false, so the body of the while is never executed.

From the tone and style of your message, I also suggest that you make a conscious effort to increase your patience and curb the need to vent out your frustration aggressively. Realize that you are constantly learning, and will always be learning, and in this sense, it's perfectly normal to come across stumbling blocks in the path. When you do, feel lucky, because you're given new opportunities to learn. Fortunately, working on algorithm problems will give you plenty of these opportunities .

Top Secret
New poster
Posts: 5
Joined: Tue Mar 12, 2013 12:31 am

### Re: 10308 - Roads in the North

Yes!!!! Got AC!
I just changed (!EOF) to (cin.peek()!=EOF)

And thanks. I have now understood my fault.. This is really the way to learn!!! !

From now, i'll be patient thinking that i am actually learning!!