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