10308  Roads in the North
Moderator: Board moderators
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.

 System administrator & Problemsetter
 Posts: 399
 Joined: Sat Jan 12, 2002 2:00 am
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;
Road,R : Array[1..MaxN]of Comp;
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;
Road[E]:=0;
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;
Road[Map.B]:=Road[Map.A]+Map.L;
if Road[Map.B]>l then begin
l:=Road[Map.B];
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;
Road[Map[i].A]:=Road[Map[i].B]+Map[i].L;
if Road[Map[i].A]>l then begin
l:=Road[Map[i].A];
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;
Readln(a,b,l);
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;
if Eoln(InPut) then Readln;
if N=0 then Readln;
i:=GetLast(1);
GetLast(i);
Writeln(l:0);
end;
end.[/pascal]
[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;
Road,R : Array[1..MaxN]of Comp;
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;
Road[E]:=0;
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;
Road[Map.B]:=Road[Map.A]+Map.L;
if Road[Map.B]>l then begin
l:=Road[Map.B];
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;
Road[Map[i].A]:=Road[Map[i].B]+Map[i].L;
if Road[Map[i].A]>l then begin
l:=Road[Map[i].A];
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;
Readln(a,b,l);
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;
if Eoln(InPut) then Readln;
if N=0 then Readln;
i:=GetLast(1);
GetLast(i);
Writeln(l:0);
end;
end.[/pascal]
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.
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
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 noncompact manner. (I misunderstood your question)
I'm sorry, I guess the cities could be numbered in a noncompact manner. (I misunderstood your question)

 Guru
 Posts: 1080
 Joined: Thu Dec 19, 2002 7:37 pm
Well, I know we're required to answer '0' in this case, but it makes no sense. The distance between two nonexistent 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'.shahriar_manzoor wrote:There can be inputs with zero cities!!!
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 )
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).little joey wrote:Well, I know we're required to answer '0' in this case, but it makes no sense. The distance between two nonexistent 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'.

 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
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)
Born from ashes  restarting counter of problems (800+ solved problems)
Dominik your algorithm is right (I got AC with same algorithm).
In this algorithm only one intersting place:
where max  is our answer and max1,max2  two maximal distances from this node ( max1 >= max2)
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;
}
INPUT:
OUTPUT:
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
Code: Select all
22
0
22
daveon wrote:INPUT:OUTPUT: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
Code: Select all
22 0 22
Why is it like that..?
Problem statement say
Two consecutive sets are separated by a blank line