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 1077. Travelling Tours

WHY WA ON FIRST TEST??? ANYBODY COULD TELL ME WHERE IS A TRICK???
Posted by hey, dude! 2 Apr 2005 20:46
Why so simple problem have so small percent of accepted??? Is there bad test? Or there is some nasty trick?

Here is my code:

var
 a : array [1..200,1..200] of byte;
 b,u,now : array [1..200] of boolean;
 p,c : array [1..200] of byte;
 v,i,j,n,m,x,y,t,r,k : longint;
procedure vvod;
begin
 read(n,m);
 for i := 1 to m do
 begin
  read(x,y);
  a[x,y] := 1;
  a[y,x] := 1;
 end; x := 0;
 fillchar(b,sizeof(b),true);
 fillchar(now,sizeof(now),true);
end;
procedure dfs(x : byte);
var
 i : byte;
begin
 now[x] := false;
 for i := 1 to n do
 if now[i] and (a[x,i] = 1) then
 begin
  p[i] := x;
  dfs(i);
 end;
end;
procedure cycle;
begin
 inc(t); k := 0;
 fillchar(u,sizeof(u),true);
 x := i;
 while (x <> 0) do
 begin
  u[x] := false; x := p[x];
 end;
 x := j;
 while (x <> 0) do
 begin
  inc(k); c[k] := x;
  if not(u[x]) then
  begin
   break; r := k;
  end;
  u[x] := false; x := p[x];
 end;
 y := i;
 while (y <> 0) and (y <> x) do
 begin
  inc(k); c[k] := x; x := p[x];
 end;
end;
procedure find;
begin
 for v := 1 to n do
 if now[v] then
 begin
  dfs(v); inc(x);
 end;
 writeln(m-n+x);
 for v := 1 to n do
 if b[v] then
 begin
  fillchar(now,sizeof(now),true);
  dfs(v);
  for i := 1 to n-1 do
  for j := i+1 to n do
  if not((p[i] = j) or (p[j] = i)) then
  begin
   if (a[i,j] = 1) and not(now[i]) and not(now[j]) then
   begin
    cycle;
    write(k);
    for x := 1 to r do write(' ',c[x]);
    for x := k downto r+1 do write(' ',c[x]);
    writeln;
   end;
  end;
  for i := 1 to n do
  if not(now[i]) then b[i] := false;
 end;
end;
begin
 vvod;
 find;
end.
Try this test (+)
Posted by Victor Barinov (TNU) 2 Apr 2005 22:08
3 3
1 2
2 2
3 1

Your program outputs:
1

It is NOT right, but I'm not sure that input is correct :)
Thanks. But still WA on first test =(
Posted by hey, dude! 4 Apr 2005 12:08
Anybody who have got AC - how did you manage with it ??? Please, give me an interecting test!

My new code (nothing new - only check for edges (x - x) :

var
 a : array [1..200,1..200] of byte;
 b,u,now : array [1..200] of boolean;
 p,c : array [1..200] of byte;
 v,i,j,n,m,x,y,t,r,k : longint;
procedure vvod;
begin
 read(n,m);
 for i := 1 to m do
 begin
  read(x,y);
  if (x <> y) then
  begin
   a[x,y] := 1;
   a[y,x] := 1;
  end
  else inc(k);
 end; x := 0;
 fillchar(b,sizeof(b),true);
 fillchar(now,sizeof(now),true);
end;
procedure dfs(x : byte);
var
 i : byte;
begin
 now[x] := false;
 for i := 1 to n do
 if now[i] and (a[x,i] = 1) then
 begin
  p[i] := x;
  dfs(i);
 end;
end;
procedure cycle;
begin
 inc(t); k := 0;
 fillchar(u,sizeof(u),true);
 x := i;
 while (x <> 0) do
 begin
  u[x] := false; x := p[x];
 end;
 x := j;
 while (x <> 0) do
 begin
  inc(k); c[k] := x;
  if not(u[x]) then
  begin
   break; r := k;
  end;
  u[x] := false; x := p[x];
 end;
 y := i;
 while (y <> 0) and (y <> x) do
 begin
  inc(k); c[k] := x; x := p[x];
 end;
end;
procedure find;
begin
 for v := 1 to n do
 if now[v] then
 begin
  dfs(v); inc(x);
 end;
 writeln(m-n+x-k);
 for v := 1 to n do
 if b[v] then
 begin
  fillchar(now,sizeof(now),true);
  dfs(v);
  for i := 1 to n-1 do
  for j := i+1 to n do
  if not((p[i] = j) or (p[j] = i)) then
  begin
   if (a[i,j] = 1) and not(now[i]) and not(now[j]) then
   begin
    cycle;
    write(k);
    for x := 1 to r do write(' ',c[x]);
    for x := k downto r+1 do write(' ',c[x]);
    writeln;
   end;
  end;
  for i := 1 to n do
  if not(now[i]) then b[i] := false;
 end;
end;
begin
 vvod;
 find;
end.
AT LAST! =) I've got AC now!
Posted by hey, dude! 4 Apr 2005 12:35
My prog have failed on a test like this :

9 10
1 2 1 3 2 3
4 5 4 6 5 6
7 8 7 9 8 9
1 9

How stupid mistake I made!!! But now I have AC =)