10308 - Roads in the North

All about problems in Volume 103. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

daveon
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 am
Location: TORONTO, CANADA

Post by daveon »

I guess the input contains empty villages.

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Post by helloneo »

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
Location: TORONTO, CANADA

Post by daveon »

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

Post by nymo »

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
Location: TORONTO, CANADA

Post by daveon »

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

Post by 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;
}
Rodrigo Alves Lima
Brazil

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Post by helloneo »

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

Post by suneast »

faint :o
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 :wink:

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

Re: 10308 - Roads in the North

Post by SyFy »

My AC program gives another output :

Code: Select all

22
0
0
22
suneast wrote:faint :o
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 :wink:

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

Re: 10308 - Roads in the North

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

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

Re: 10308 - Roads in the North

Post by ?????? ???? »

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:

Post by DD »

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

Post by Top Secret »

:evil: :evil: :evil: :evil: :evil: :evil: :evil: :evil: :evil: :evil: :evil: :evil:

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

Post by lbv »

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

Post by Top Secret »

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

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

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

Post Reply

Return to “Volume 103 (10300-10399)”