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 1176. Hyperchannels

WA on #3, help please, MLE on #12
Posted by Danica Porobic 1 Jul 2004 18:10
var
  g:array[1..1000,1..1000] of Boolean;
  i,j,n,a,k,s:smallint;
procedure find(i:smallint);
var
  j:smallint;
begin
  for j:=n downto 1 do
    if g[i,j] then
      begin
        g[i,j]:=false;
        find(j)
      end;
  if s<>0 then
    writeln(s,' ',i);
  s:=i;
end;
begin
  assign(input,'');
  reset(input);
  readln(n,a);
  for i:=1 to n do
    for j:=1 to n do
      begin
        read(k);
        g[i,j]:=(k=0) and (i<>j)
      end;
  close(input);
  s:=0;
  find(a);
end.

If I put s in memory and write it in reverse order I get MLE on test 12:
var
  g:array[1..1000,1..1000] of Boolean;
  i,j,n,a,k,st:smallint;
  s:array[1..32000] of smallint;
procedure find(i:smallint);
var
  j:smallint;
begin
  for j:=n downto 1 do
    if g[i][j] then
      begin
        g[i][j]:=false;
        find(j)
      end;
  inc(st);
  s[st]:=i
end;
begin
  assign(input,'');
  reset(input);
  readln(n,a);
  for i:=1 to n do
    for j:=1 to n do
      begin
        read(k);
        g[i][j]:=(k=0) and (i<>j)
      end;
  close(input);
  st:=0;
  find(a);
  for i:=st-1 downto 1 do
    writeln(s[i+1],' ',s[i]);
end.

Please help me solve either of this two problems.
Re: WA on #3, help please, MLE on #12
Posted by Sergey Simonchik 16 Jul 2004 15:40
There are two way to accept it:
1. Use stack instead of recursion.
2. Use recursion without variable "j".

In all cases you can use array "st" and don't worry about memory limit.
Re: WA on #3, help please, MLE on #12
Posted by Gheorghe Stefan 16 Jul 2004 19:55
you can use dynamic lists for the graph instead of that bool matrix...