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

Shit !!! How CAN' T i Memory Limit Exceeded???
Posted by Register 22 Dec 2007 16:38
program p1039;// Use DP, but Memory Limit Exceeded.
// for this one program,
// i have got 35423 KB, 25635 KB, or even 17495 KB,
// but never 16384 KB...
// what a pity!!!

var
  g:array[1..6000,1..6000]of boolean;
  y:array[1..6000]of boolean;
  v:array[1..6000]of integer;
  tree,son:array[1..6000,0..6000]of word;
  f:array[1..6000,1..2]of longint;
  n,i,j,k,t,xx,yy,ans,p:longint;

function max(a,b:longint):longint;
  begin
    if a>b
      then max:=a else max:=b;
  end;

begin
  fillchar(g,sizeof(g),false);
  readln(n);
  for i:=1 to n do readln(v[i]);
  readln(xx,yy);
  while (xx>0) do
  begin
    g[xx,yy]:=true;
    g[yy,xx]:=true;
    readln(xx,yy);
  end;

  fillchar(y,sizeof(y),true);
  fillchar(tree,sizeof(tree),0);
  fillchar(son,sizeof(son),0);
  y[1]:=false; p:=1;
  tree[1,0]:=1;tree[1,1]:=1;

  while tree[p,0]>0 do
  begin
    for i:=1 to tree[p,0] do
      for j:=1 to n do
        if (y[j] and g[tree[p,i],j])
          then begin
            inc(tree[p+1,0]);
            tree[p+1,tree[p+1,0]]:=j;
            y[j]:=false;
            inc(son[tree[p,i],0]);
            son[tree[p,i],son[tree[p,i],0]]:=j;
          end;
    inc(p);
  end;

  for i:=p-1 downto 1 do
    for j:=1 to tree[i,0] do
    begin
      t:=tree[i,j];
      f[t,1]:=v[t];
      f[t,2]:=0;
      for k:=1 to son[t,0] do
      begin
        f[t,1]:=f[t,1]+f[son[t,k],2];
        f[t,2]:=f[t,2]+max(f[son[t,k],1],f[son[t,k],2]);
      end;
    end;
  ans:=max(f[1,1],f[1,2]);
  writeln(ans);
end.

Edited by author 22.12.2007 16:39
Re: Shit !!! How CAN' T i Memory Limit Exceeded???
Posted by Alias (Alexander Prudaev) 22 Dec 2007 21:52
you don't need so big array as son or tree
array [1..n, 1..n] is too big.

all you need is several arrays [1..n]
for example you can store for each vertex
his parent, leftmost child and rightmost brother.
another way is to use lists of childs. sum of all lengths of
these lists will be N - 1, so it is O(n) memory, not n^2
the second way is better.
you can find "linked list" data structure, for example in google

type
  pnode = ^node;
  node = record
    x: integer;
    next: pnode;
  end;

procedure add(var p: pnode; x: integer);
var t: pnode;
begin
  new(t);
  t^.x := x;
  t^.next := p;
  p := t;
end;

var
  s, t: pnode;
  i: Integer;
begin
  s := nil;
  for i := 1 to 10 do add(s, i);
  t := s;
  while (t <> nil) do
  begin
    writeln(t^.x);
    t := t^.next;
  end;
  readln;
end.
Re: Shit !!! How CAN' T i Memory Limit Exceeded???
Posted by Register 23 Dec 2007 10:45
Thanks a lot.
Re: Shit !!! How CAN' T i Memory Limit Exceeded???
I can tell you the answer!
program rabidstorm1039;
const
  maxn=6000;
var
  pres:array[1..maxn]of boolean;{True if he can be president}
  now,child,pre:array[1..maxn]of word;
  yes,no:array[1..maxn]of longint;
  n,i,x,y:word;
  root:longint;
function max(a,b:longint):longint;
  begin
    if a>b then max:=a else max:=b;
  end;
procedure dfs(v:word);
  begin
    while now[v]>0 do begin
      dfs(child[now[v]]);
      inc(yes[v],no[child[now[v]]]);
      inc(no[v],max(yes[child[now[v]]],no[child[now[v]]]));
      now[v]:=pre[now[v]];
    end;
  end;
begin
  read(n);
  for i:=1 to n do
    read(yes[i]);
  fillchar(pres,sizeof(pres),1);
  root:=n*(n+1) div 2;
  for i:=1 to n-1 do begin
    read(x,y);
    child[i]:=x;
    pre[i]:=now[y];
    now[y]:=i;
    if pres[x] then begin
      dec(root,x);
      pres[x]:=false;
    end;
  end;

  dfs(root);

  writeln(max(yes[root],no[root]));
end.