ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1039. Юбилейная вечеринка

Can anyone help me? I have a few questions about this problem.
Послано Paragina Silviu 14 апр 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.
Послано TheBlaNK 14 апр 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]++;
  }
}