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

Обсуждение задачи 1077. Travelling Tours

WHY WA ON FIRST TEST??? ANYBODY COULD TELL ME WHERE IS A TRICK???
Послано hey, dude! 2 апр 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 (+)
Послано Victor Barinov (TNU) 2 апр 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 =(
Послано hey, dude! 4 апр 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!
Послано hey, dude! 4 апр 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 =)