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 1039. Anniversary Party

Can anyone help me? I have a few questions about this problem.
Posted by Paragina Silviu 14 Apr 2003 04:13
if it is a hierarchical structure, rooted at the president that
means that the strucure is a tree. Well if it is a tree there should
be only n-1  connections why does it have to end with 0 0.

My program reads only n-1 line after the conviviality ratings. Is
thits why i get WA or what is it. Pls help


program party;
var     p,nf   :array[1..6000] of integer;
{p[i] supervisor of i}
{nf number of "sons"}
        cu,fa  :array[1..6000] of longint;
{cu[i] maximum conviviality rating when employee i comes to the party
fa[i] maximum conviviality rating when employee i stays home}
        cov    :array[1..6000] of integer;
        nx,cr,n,i,last:integer;
{cr current leaf
nx next leaf}
{every time we analyze a leaf we cut it from the tree}
{doing that at a time another node will becom a leaf}
begin
        read(n);
        fillchar(nf,12000,0);
        fillchar(fa,24000,0);
        fillchar(cu,24000,0);
        fillchar(p ,12000,0);
        for i:=1 to n do
        begin
                read(cov[i]);
        end;
        cu[1]:=cov[1];
        for i:=2 to n do
        begin
                read(cr,nx);
                inc(nf[nx]);
                p[cr]:=nx;
                cu[i]:=cov[i];
        end;
        i:=1;
{search for the first leaf}
        while (nf[i]>0) do inc(i);
        cr:=i;
        inc(i);
{search for the next if it exists}
        while (nf[i]>0) and (i<=n) do inc(i);
        nx:=i;
        while true do
        begin
                if p[cr]>0 then
                begin
                        cu[p[cr]]:=fa[cr]+cu[p[cr]];
                        if fa[cr]>cu[cr] then
                                fa[p[cr]]:=fa[p[cr]]+ fa[cr] else
                                fa[p[cr]]:=fa[p[cr]]+ cu[cr];
                        dec(nf[p[cr]]);
                        cr:=p[cr];
                        if (cr>nx) or (nf[cr]<>0) then
                        begin
                                {execute if the father doesn't
become a leaf or the father is bigger than nx, otherwise process the
father}
                                cr:=nx;
                                inc(nx);
                                while (nx<=n) and (nf[nx]>0)  do inc
(nx);
                        end;
                end else break;
        end;
{when father of cr is 0 cr is the president}
        writeln(cu[cr]);
end.



PS sorry for my english
Re: Can anyone help me? I have a few questions about this problem.
Posted by TheBlaNK 14 Apr 2003 16:56
my program read n-1 line
and got AC
there are something wrong with your program na :)

void input(void)
{
 long i;
 fscanf(fp,"%ld",&n);
 for(i=1;i<=n;i++) fscanf(fp,"%ld",&rate[i]);
 for(i=1;i<n;i++)
  { fscanf(fp,"%ld %ld",&con[i].l,&con[i].k);
    deg[con[i].l]++;
  }
}