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

Common Board

To Rybak Michael. Please, give me some hints and tests for problem 1109(Conference). I don't know why I get WA :-( (++)
Posted by Nazarov Denis (nsc2001@rambler.ru) 8 Feb 2002 21:00
My program:

Program t1109;

Const MaxN=1000;

Var   G         : array[1..MaxN,1..MaxN]of byte;
      M,N,K     : longint;
      i,j,k1,k2 : longint;
      Ans       : longint;
      Sm,Sn     : array[1..MaxN]of longint;
      Mx,Nx     : longint;
      Om,On     : array[1..MaxN]of byte;
      ex        : boolean;

Procedure Add_m(mnum : longint); forward;
Procedure Add_n(nnum : longint); forward;

Procedure Del_m(mnum : longint);
Var i : longint;
 begin
  for i:=1 to M do
   if G[mnum,i]=1 then begin
    if Sn[i]=1 then Add_n(i) else Sn[i]:=Sn[i]-1;
    G[mnum,i]:=0;
   end;
 end;

Procedure Del_n(nnum : longint);
Var j : longint;
 begin
  for j:=1 to N do
   if G[j,nnum]=1 then begin
    if Sm[j]=1 then Add_m(j) else Sm[j]:=Sm[j]-1;
    G[j,nnum]:=0;
   end;
 end;

Procedure Add_m(mnum : longint);
Var j,jk : longint;
 begin
  Ex:=false;
  Ans:=Ans+1;
  for j:=1 to N do
   if G[mnum,j]=1 then begin
    jk:=j;
    break;
   end;
  G[mnum,jk]:=0;
  Om[mnum]:=1;
  On[jk]:=1;
  Sm[mnum]:=0;
  Sn[jk]:=Sn[jk]-1;
  if Sn[jk]>0 then Del_n(jk);
 end;

Procedure Add_n(nnum : longint);
Var i,ik : longint;
 begin
  Ex:=false;
  Ans:=Ans+1;
  for i:=1 to M do
   if G[i,nnum]=1 then begin
    ik:=i;
    break;
   end;
  G[ik,nnum]:=0;
  On[nnum]:=1;
  Om[ik]:=1;
  Sn[nnum]:=0;
  Sm[ik]:=Sm[ik]-1;
  if Sm[ik]>0 then Del_m(ik);
 end;

begin
 Assign(input,'1109.in');Reset(input);
 FillChar(G,SizeOf(G),0);
 FillChar(Sm,SizeOf(Sm),0);
 FillChar(Sn,SizeOf(Sn),0);
 FillChar(Om,SizeOf(Om),0);
 FillChar(On,SizeOf(On),0);
 Read(M,N,K);
 for i:=1 to K do begin
   Read(k1,k2);
   G[k1,k2]:=1;
   Sm[k1]:=Sm[k1]+1;
   Sn[k2]:=Sn[k2]+1;
  end;
 Ans:=0;
 Repeat
  Ex:=true;
  for i:=1 to M do
   if Om[i]=0 then
    if Sm[i]=1 then
     Add_m(i);
  for i:=1 to N do
   if On[i]=0 then
    if Sn[i]=1 then
     Add_n(i);
 Until Ex;
 Mx:=0;
 Nx:=0;
 for i:=1 to M do if Om[i]=0 then Mx:=Mx+1;
 for i:=1 to N do if On[i]=0 then Nx:=Nx+1;
 if Mx>Nx then Ans:=Ans+Mx else Ans:=Ans+Nx;
 if (M=0)or(N=0) then Ans:=0;
 Writeln(Ans);
end.

I have been dubuging my program since 1st January but with no result.
May be my alogrithm is wrong(I think that this program should get TL,
but not WA),though I work at problem 1159 much more.