結果

問題 No.2696 Sign Creation
ユーザー timitimi
提出日時 2024-02-05 09:47:41
言語 PyPy3
(7.3.15)
結果
MLE  
(最新)
AC  
(最初)
実行時間 -
コード長 2,552 bytes
コンパイル時間 132 ms
コンパイル使用メモリ 82,728 KB
実行使用メモリ 622,120 KB
最終ジャッジ日時 2024-05-17 18:10:03
合計ジャッジ時間 13,761 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 43 ms
60,920 KB
testcase_01 AC 43 ms
60,544 KB
testcase_02 AC 35 ms
54,956 KB
testcase_03 AC 38 ms
59,968 KB
testcase_04 AC 36 ms
53,944 KB
testcase_05 AC 39 ms
60,668 KB
testcase_06 AC 35 ms
53,916 KB
testcase_07 AC 34 ms
52,876 KB
testcase_08 AC 153 ms
99,612 KB
testcase_09 AC 60 ms
70,312 KB
testcase_10 AC 128 ms
84,744 KB
testcase_11 AC 70 ms
76,340 KB
testcase_12 AC 69 ms
76,296 KB
testcase_13 AC 1,304 ms
289,888 KB
testcase_14 AC 572 ms
136,752 KB
testcase_15 AC 490 ms
142,868 KB
testcase_16 AC 1,336 ms
318,684 KB
testcase_17 AC 190 ms
82,412 KB
testcase_18 AC 249 ms
86,296 KB
testcase_19 AC 489 ms
123,580 KB
testcase_20 AC 77 ms
76,448 KB
testcase_21 AC 481 ms
132,592 KB
testcase_22 AC 318 ms
86,888 KB
testcase_23 AC 504 ms
122,004 KB
testcase_24 AC 467 ms
122,120 KB
testcase_25 AC 519 ms
124,104 KB
testcase_26 AC 222 ms
83,640 KB
testcase_27 AC 265 ms
85,140 KB
testcase_28 AC 239 ms
86,152 KB
testcase_29 AC 212 ms
83,504 KB
testcase_30 AC 214 ms
84,580 KB
testcase_31 MLE -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
testcase_35 -- -
testcase_36 -- -
testcase_37 -- -
testcase_38 -- -
testcase_39 -- -
testcase_40 -- -
権限があれば一括ダウンロードができます

ソースコード

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