LEM2 - GUMBI

Tác giả: RR

Ngôn ngữ: Pascal

{$R-,Q-}
const
  FINP='';
  FOUT='';
  MAXN=20;
  oo=1000000;
var
  first,last,k,n:longint;
  a:array[1..MAXN] of longint;
  queue,d:array[0..1048577] of longint;
procedure inp; inline;
var
  f:text;
  i,j,jj,x:longint;
begin
  assign(f,FINP); reset(f);
  read(f,n,k);
  for i:=1 to n do
    begin
      read(f,j);
      for jj:=1 to j do
        begin
          read(f,x);
          if (a[i] shr (x-1)) and 1=0 then a[i]:=a[i]+1 shl (x-1);
        end;
      a[i]:=not a[i];
    end;
  j:=0;
  for i:=1 to n do
    begin
      read(f,x);
      if x=1 then j:=j+1 shl (i-1);
    end;
  for i:=1 shl n downto 0 do d[i]:=oo;
  first:=1; last:=1; queue[1]:=j;
  d[j]:=0;
  close(f);
end;
procedure solve; inline;
var
  u,i,uu:longint;
begin
  while first<=last do
    begin
      u:=queue[first]; inc(first);
      for i:=1 to n do
        begin
          uu:=(u or (1 shl (i-1))) and a[i];
          if d[uu]=oo then
            begin
              d[uu]:=d[u]+1;
              inc(last); queue[last]:=uu;
              if uu=1 shl (k-1) then exit;
            end;
        end;
    end;
end;
procedure ans; inline;
var
  f:text;
begin
  assign(f,FOUT); rewrite(f);
  if d[1 shl (k-1)]<oo then writeln(f,d[1 shl (k-1)])
  else writeln(f,-1);
  close(f);
end;
begin
  inp;
  solve;
  ans;
end.

Download