## 10308 - Roads in the North

Moderator: Board moderators

Joe Smith
New poster
Posts: 26
Joined: Wed Apr 17, 2002 5:56 am

### 10308 - Roads in the North

Am I wrong in assuming the graph is a tree? I interpret the statement "there is only one route from a village to a village that does not pass through some other village twice" as meaning there are no cycles, and it says there's only 1 component. If this is right then it's easy, just dfs, but I'm getting WA.

shahriar_manzoor
Posts: 399
Joined: Sat Jan 12, 2002 2:00 am
There can be inputs with zero cities!!!

Joe Smith
New poster
Posts: 26
Joined: Wed Apr 17, 2002 5:56 am
shahriar_manzoor wrote:There can be inputs with zero cities!!!
Oops, I guess I can't read.

Thanks!

Revenger
Experienced poster
Posts: 132
Joined: Sun Apr 14, 2002 12:27 pm
Location: Russia
I use DFS. But Can anybody say why this program get WA?

[pascal]Program p10308;

Const MaxN = 10000;
p1 = 5000;
p2 = 500;

Type Comp = Integer;

Var Map : Array[1..MaxN]of Record A,B : Integer; L : Comp; End;
list,p : Array[0..MaxN]of Integer;
i,N,M : Integer;
a,b,j : Integer;
lmin : Integer;
min,mid : Comp;
l,max : Comp;
tt : byte;

Function GetLast(E : Integer) : Integer;
Var Use : Array[1..MaxN]of byte;
i,j : Integer;
ok : Byte;
begin
FillChar(Use,SizeOf(Use),0);
Use[E]:=1;
l:=0;
GetLast:=E;
While True Do begin
ok:=1;
for i:=1 to M do
if (Use[Map.A]=1)and(Use[Map.B]=0) then begin
ok:=0;
Use[Map.B]:=1;
GetLast:=Map.B;
end;
end else
if (Use[Map.A]=0)and(Use[Map[i].B]=1) then begin
ok:=0;
Use[Map[i].A]:=1;
GetLast:=Map[i].A;
end;
end;
if ok=1 then Break;
end;
end;

begin
While Not Eof(InPut) Do begin
N:=0;
M:=0;
i:=1;
While True do begin
if (Eof(InPut))or(Eoln(InPut)) then Break;
if a>N then N:=a;
if b>N then N:=b;
Map[i].A:=a;
Map[i].B:=b;
Map[i].L:=l;
i:=i+1;
M:=M+1;
if (Eof(InPut))or(Eoln(InPut)) then Break;
end;
i:=GetLast(1);
GetLast(i);
Writeln(l:0);
end;
end.[/pascal]

Rivaldo
New poster
Posts: 19
Joined: Sun Jul 07, 2002 3:59 pm

### 10308

It says "The villages are numbered from 1."
Does it mean the villages are numberd 1, 2, 3, 4, ..., n, when the number of village is n.

Maxim
New poster
Posts: 38
Joined: Tue Aug 27, 2002 12:36 am
Location: Croatia
Contact:
What like looks input case when there are zero villages? Is it a blank line, or it consists of line with 0 for village i or j? Please, help. I've solved it and tested it on my computer, but when I send it, it gets Runtime Error (Invalid memory reference). I decrease index of each vilage after scaning it. Upper bound sure doesn't make any trouble.

scythe
New poster
Posts: 12
Joined: Mon Oct 07, 2002 12:25 pm

### Re:

Uhm.. yeah

ithamar
Learning poster
Posts: 56
Joined: Mon May 13, 2002 11:58 pm
Location: Venezuela
I has not solved this problem but from the problem statement i cant asure that the cities are numered sequentially 1, 2, ..., n. Maybe some data set could be 1, 2, 6, 12, maybe not. But the problem statement leave the second posibility open so you shuld take care of.
Those Who Don't Know History are doomed to repeat it

scythe
New poster
Posts: 12
Joined: Mon Oct 07, 2002 12:25 pm

### Ah, could be right

I got ac, but my source code works for that kind of tests.
I'm sorry, I guess the cities could be numbered in a non-compact manner. (I misunderstood your question)

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
shahriar_manzoor wrote:There can be inputs with zero cities!!!
Well, I know we're required to answer '0' in this case, but it makes no sense. The distance between two non-existent cities is zero? That's only because one particular implementation of an algorithm to solve this problem would answer '0'. Mathematical sense would give 'undefined'.

It's a pitty to see a perfect problem spoiled by this kind of nonsense.

(Shahriar, I know you're not the problemsetter, just the messenger; this is not a personal attack )

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden
little joey wrote:Well, I know we're required to answer '0' in this case, but it makes no sense. The distance between two non-existent cities is zero? That's only because one particular implementation of an algorithm to solve this problem would answer '0'. Mathematical sense would give 'undefined'.
It would also be consistent with mathematical sense (more so than letting it be undefined, in my opinion) to define the distance as negative infinity in such cases (cf. the degree of the zero polynomial, for example).

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
I use DFS() to solve this problem, but I got WA several times ...
Is any trap in this problem ?
My program outputs 0 when input has na cities. When I traverse graph in every node I remember two maximal distances from this node to any children. Sum of this values in every node is maximal distance between nodes. If I compute all nodes, I should get correct answer. Of course if graph is connected ... Am I wrong with this algorithm ? Could anyone help me ?

Best regards
DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

artem
New poster
Posts: 17
Joined: Thu Jun 09, 2005 5:01 pm
Dominik your algorithm is right (I got AC with same algorithm).
In this algorithm only one intersting place:

Code: Select all

``````DFS(...){
int max1=0,max2=0,.....;
......  // cycle
t=DFS(.....);
if (t > max1){
max2=max1;
max1=t;
}
else  if (t > max2) max2=t;
....... // end cycle
if (max1+max2 > max) max=max1+max2;
return max1;
}
``````
where max - is our answer and max1,max2 - two maximal distances from this node ( max1 >= max2)

daveon
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 am
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
``````

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea
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
``````

Why is it like that..?
Problem statement say
Two consecutive sets are separated by a blank line