ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1018. Binary Apple Tree

WA
Posted by Le Phuoc Hai Son 20 Jun 2001 19:36
I don't know why i am get WA.
Admin can you send me any tests and solutions.
Anyone can help me find the errors:

{I use dynamic programming}
Program ACM1018;
Const max=100;
Var n,q,t:byte;
    qhd:array[0..max,0..max] of longint;
    mg1:array[0..100] of record
rank,n1,n2:byte;app:integer;end;
    mg:array[1..100] of record i,j:byte;k:integer;end;

Procedure readin;
Var i,count:byte;
Begin
     Readln(n,q);if q=n then q:=n-1;
     For i:=1 to n-1 do
         begin
         readln(mg[i].i,mg[i].j,mg[i].k);
         end;
     {********}
     count:=n-1;t:=1;
     fillchar(mg1,sizeof(mg1),0);mg1[1].rank:=1;
     Repeat
           For i:=1 to n-1 do
               begin
                    if (mg1[mg[i].i].rank=t) and (mg1[mg
[i].j].rank=0) then
                       begin
                            if mg1[mg[i].i].n1=0 then mg1[mg
[i].i].n1:=mg[i].j
                                                 else if mg1
[mg[i].i].n2=0 then mg1[mg[i].i].n2:=mg[i].j;
                            mg1[mg[i].j].app:=mg[i].k;
                            mg1[mg[i].j].rank:=t+1;dec
(count);
                       end;
                    if (mg1[mg[i].j].rank=t) and (mg1[mg
[i].i].rank=0) then
                       begin
                            if mg1[mg[i].j].n1=0 then mg1[mg
[i].j].n1:=mg[i].i
                                                 else if mg1
[mg[i].j].n2=0 then mg1[mg[i].i].n2:=mg[i].i;
                            mg1[mg[i].i].app:=mg[i].k;
                            mg1[mg[i].i].rank:=t+1;dec
(count);
                       end;
               end;
           inc(t);
     Until count=0;

End;

Procedure dynamic;
Var i,j,k,l,m:byte;temp:longint;
Begin
     fillchar(qhd,sizeof(qhd),0);
     For i:=t downto 1 do
         Begin
              For j:=1 to n do
                  if mg1[j].rank=i then
                  begin
                  if mg1[j].n1=0 then begin qhd[j,1]:=mg1
[j].app;qhd[j,0]:=1;end
                  else
                  begin
                       qhd[j,1]:=mg1[j].app;qhd[j,0]:=1;
                       if qhd[mg1[j].n1,0]>0 then For k:=1
to qhd[mg1[j].n1,0] do
                           begin
                                if qhd[j,k+1]<qhd[mg1
[j].n1,k]+mg1[j].app then qhd[j,k+1]:=qhd[mg1[j].n1,k]+mg1
[j].app;
                                if k+1>qhd[j,0] then qhd
[j,0]:=k+1;
                                if qhd[mg1[j].n2,0]>0 then
For l:=1 to qhd[mg1[j].n2,0] do
                                    begin
                                        if qhd[j,l+1]<qhd
[mg1[j].n2,l]+mg1[j].app then qhd[j,l+1]:=qhd[mg1[j].n2,l]
+mg1[j].app;
                                        if l+1>qhd[j,0]
then qhd[j,0]:=l+1;
                                        m:=k+l+1;
                                        if m>qhd[j,0] then
qhd[j,0]:=m;
                                        temp:=qhd[mg1
[j].n1,k]+qhd[mg1[j].n2,l]+mg1[j].app;
                                        if qhd[j,m]<temp
then qhd[j,m]:=temp;
                                    end;

                           end;
                       if qhd[j,0]>q-mg1[j].rank+2 then qhd
[j,0]:=q-mg1[j].rank+2;
                       if qhd[j,0]<0 then qhd[j,0]:=0;
                  end;
                  end;
         End;
End;

Begin
     readin;
     dynamic;
     writeln(qhd[1,q+1]);
End.
you wanna get the test data and solutions from admins ??? dream on !
Posted by Dinh Quang Hiep (mg9h@yahoo.com) 20 Jun 2001 19:54
i'll answer you about your source later, just be a
little patient ;)

QH@
You just wasted three spaces for one message. That's a big waste of space!!!
Posted by Petko Minkov 22 Jun 2001 03:29
   if m>qhd[j,0] then
> qhd[j,0]:=m;
>                                         temp:=qhd[mg1
> [j].n1,k]+qhd[mg1[j].n2,l]+mg1[j].app;
>                                         if qhd[j,m]<temp
> then qhd[j,m]:=temp;
>                                     end;
>
>                            end;
>                        if qhd[j,0]>q-mg1[j].rank+2 then
qhd
> [j,0]:=q-mg1[j].rank+2;
>                        if qhd[j,0]<0 then qhd[j,0]:=0;
>                   end;
>                   end;
>          End;
> End;
>
> Begin
>      readin;
>      dynamic;
>      writeln(qhd[1,q+1]);
> End.
Re: You just wasted three spaces for one message. That's a big waste of space!!!
Posted by aaa 6 Jul 2001 10:27
>    if m>qhd[j,0] then
> > qhd[j,0]:=m;
> >                                         temp:=qhd[mg1
> > [j].n1,k]+qhd[mg1[j].n2,l]+mg1[j].app;
> >                                         if qhd[j,m]
<temp
> > then qhd[j,m]:=temp;
> >                                     end;
> >
> >                            end;
> >                        if qhd[j,0]>q-mg1[j].rank+2 then
> qhd
> > [j,0]:=q-mg1[j].rank+2;
> >                        if qhd[j,0]<0 then qhd[j,0]:=0;
> >                   end;
> >                   end;
> >          End;
> > End;
> >
> > Begin
> >      readin;
> >      dynamic;
> >      writeln(qhd[1,q+1]);
> > End.