結果

問題 No.2696 Sign Creation
コンテスト
ユーザー timi
提出日時 2024-02-05 09:47:41
言語 PyPy3
(7.3.15)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 2,552 bytes
コンパイル時間 271 ms
コンパイル使用メモリ 82,524 KB
実行使用メモリ 686,504 KB
最終ジャッジ日時 2024-12-20 11:54:55
合計ジャッジ時間 16,815 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 36 TLE * 1 MLE * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
  from sys import stdin, setrecursionlimit
  input = stdin.readline
  readline = stdin.readline

  H,W,N,D=map(int, input().split())
  A=[[-1]*W for _ in range(H)]
  C=[]
  for i in range(N):
    h,w=map(int, input().split())
    h-=1;w-=1
    C.append((h,w))
    A[h][w]=i
    
  B=[]
  for i in range(-D,D+1):
    for j in range(-D,D+1):
      if abs(i)+abs(j)<=D:
        B.append((i,j))
        
  class RollbackUnionFind():
      def __init__(self,size):
          self.uf=[[-1,0,1,True] for i in range(size)]
          self.ope=[]
          
      def unite(self,fir,sec):
          one=self.root(fir)
          two=self.root(sec)
          self.ope.append((0,(one,self.uf[one][:]),(two,self.uf[two][:])))
          if one!=two:
              if self.uf[one][1]>self.uf[two][1]:
                  one,two=two,one
              self.uf[one][0]=two
              self.uf[two][2]+=self.uf[one][2]
              self.uf[two][3]=self.uf[one][3]&self.uf[two][3]
              if self.uf[one][1]==self.uf[two][1]:
                  self.uf[two][1]+=1
          else:
              self.uf[one][3]=False
      
      def same(self,fir,sec):
          return self.root(fir)==self.root(sec)
      
      def root(self,node):
          pos=node
          while self.uf[pos][0]!=-1:
              pos=self.uf[pos][0]
          return pos
      
      def size(self,node):
          return self.uf[self.root(node)][2]
      
      def undo(self):
          if len(self.ope)>0:
              use=self.ope.pop()
              for i,j in use[1:]:
                  self.uf[i]=j[:]
                  
  uni=RollbackUnionFind(N+1)
  
  for h in range(H):
    for w in range(W):
      if A[h][w]==-1:
        continue 
      p=A[h][w]
      for x,y in B:
        nh,nw=h+x,w+y
        if 0<=nh<H and 0<=nw<W and A[nh][nw]!=-1:
          q=A[nh][nw]
          uni.unite(p,q)
          
  D={};cnt=0
  for i in range(N):
    d=uni.root(i)
    if d not in D:
      D[d]=1
      if uni.size(d)!=1:
        cnt+=1
  
  ans=[cnt]
  for h in range(H):
    for w in range(W):
      if A[h][w]!=-1:
        continue
      c=0;p=0
      for x,y in B:
        nh,nw=h+x,w+y
        if 0<=nh<H and 0<=nw<W and A[nh][nw]!=-1:
          q=A[nh][nw]
          if not uni.same(N,q):
            a,b=uni.size(N),uni.size(q)
            if a==1 and b==1:
              p+=1
            elif a!=1 and b!=1:
              p-=1
            uni.unite(N,q)
            c+=1
      ans.append(cnt+p)
      for i in range(c):
        uni.undo()
  print(min(ans),max(ans))
main()
0