10308 - Roads in the North

[daveon]

I guess the input contains empty villages.

[helloneo]

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]

I agree, three empty lines would make a lot more sense. But I suppose an empty village takes up two lines.

[nymo]

I get ACC assuming 3 empty lines for the above test case.

[daveon]

There must be something fishy about the io for this problem. Hmmm...

[ral]

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;
}

[helloneo]

Finally got AC..~!
My program failed on this case..

Code: Select all

1 2 3
2 3 3
3 4 3

[suneast]

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]

My AC program gives another output :

Code: Select all

22
0
0
22

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]

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... :) 

[?????? ????]

Code: Select all

Remove After Accepted

[DD]

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.

[Top Secret]

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

Code: Select all

while(1) return Thanks.. 

[lbv]

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]

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!!