結果

問題 No.2696 Sign Creation
コンテスト
ユーザー watacco
提出日時 2025-10-21 22:19:30
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 5,374 bytes
コンパイル時間 454 ms
コンパイル使用メモリ 82,600 KB
実行使用メモリ 99,320 KB
最終ジャッジ日時 2025-10-21 22:19:38
合計ジャッジ時間 7,693 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 21 WA * 12 RE * 5
権限があれば一括ダウンロードができます

ソースコード

diff # 

# 10_21 2回目最初の１次元変換の掛け算ミスを修正
h,w,n,d=map(int,input().split())
mh_1=[-w,+w,+1,-1]
mh_2=[-w,+w,+1,-1,+2,-2,-2*w,+2*w,-(w-1),-(w+1),+(w-1),+(w+1)]
mh_3=[+1,-1,+2,-2,+3,-3,-w,+w,-2*w,+2*w,-3*w,+3*w,-w+1,+w+1,-2*w+1,+2*w+1,-w+2,+w+2,-w-1,+w-1,-2*w-1,+2*w-1,-w-2,+w-2]
mh_4=[+1,-1,+2,-2,+3,-3,+4,-4,-w,+w,-2*w,+2*w,-3*w,+3*w,+4*w,-4*w,-w+1,+w+1,-2*w+1,+2*w+1,-w+2,+w+2,-w-1,+w-1,-2*w-1,+2*w-1,-w-2,+w-2,-3*w+1,-2*w+2,-w+3,+w+3,+2*w+2,+3*w+1,-3*w-1,-2*w-2,-w-3,+w-3,+2*w-2,+3*w-1]
mh_5=[+1,-1,+2,-2,+3,-3,+4,-4,+5,-5,-w,+w,-2*w,+2*w,-3*w,+3*w,+4*w,-4*w,+5*w,-5*w,-w+1,+w+1,-2*w+1,+2*w+1,-w+2,+w+2,-w-1,+w-1,-2*w-1,+2*w-1,-w-2,+w-2,-3*w+1,-2*w+2,-w+3,+w+3,+2*w+2,+3*w+1,-3*w-1,-2*w-2,-w-3,+w-3,+2*w-2,+3*w-1,
-4*w+1,+4*w+1,-4*w-1,+4*w-1,-3*w+2,+3*w+2,-3*w-2,+3*w-2,-2*w+3,+2*w+3,-2*w-3,+2*w-3,-w+4,+w+4,-w-4,+w-4]

mh=[mh_1,mh_2,mh_3,mh_4,mh_5]
#計算量O(280)?

from collections import defaultdict

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
        
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        
        if x == y:
            return
        
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    
    def size(self, x):
        return -self.parents[self.find(x)]
        
    def same(self, x, y):
        return self.find(x) == self.find(y)
    
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())
    
    def all_group_members(self):
        group_members = defaultdict(list)
        for member in range(self.n):
            group_members[self.find(member)].append(member)
        return group_members
    
    def __str__(self):
        return '\n'.join(f'{r}: {m}' for r, m in self.all_group_members().items())


class UnionFindLabel(UnionFind):
    def __init__(self, labels):
        assert len(labels) == len(set(labels))
        
        self.n = len(labels)
        self.parents = [-1] * self.n
        self.d = {x: i for i, x in enumerate(labels)}
        self.d_inv = {i: x for i, x in enumerate(labels)}
    
    def find_label(self, x):
        return self.d_inv[super().find(self.d[x])]
    
    def union(self, x, y):
        super().union(self.d[x], self.d[y])
    
    def size(self, x):
        return super().size(self.d[x])
    
    def same(self, x, y):
        return super().same(self.d[x], self.d[y])
    
    def members(self, x):
        root = self.find(self.d[x])
        return [self.d_inv[i] for i in range(self.n) if self.find(i) == root]
    
    def roots(self):
        return [self.d_inv[i] for i, x in enumerate(self.parents) if x < 0]
    
    def all_group_members(self):
        group_members = defaultdict(list)
        for member in range(self.n):
            group_members[self.d_inv[self.find(member)]].append(self.d_inv[member])
        return group_members

uf = UnionFind(h*w)
star=[]
star_ck=[0]*(h*w+1)
for i in range(n):
  x,y=map(int,input().split())
  now=(x-1)*w+y
  star.append(now)
  star_ck[now]=1
#星を管理 計算量10**5 + 280？

for i in star:
  for m in mh[d-1]:
    if i+m < h*w+1 and i+m > 0 and star_ck[i+m] == 1: 
      uf.union(i,i+m)
#星をくっつける n*60 なので最大10**5 * 60 = 10**5 *6
#ここまでで10**5 *6 + 10**2 *3 + 10**5 = 700300

#if文、とりあえずくっつけてるけど範囲外が先に出て怒られそうなら、最初の二つのand条件で分岐させる
#最大値：周りで新しい星座を爆誕させられるか +1 or +0
#最小値：周りにどれだけ多い星座があってくっつけられるか -?
star_min=0
star_max=0

for i in range(1,h*w): #星がなかったらそこに星を置くと仮定してチェック開始
  if star_ck[i]==0:
    watacco={} #もうくっつけた星座かどうか見た方がいいんじゃないかな〜
    now="ONLY" #1つ星同士しかくっつけてないかどうか？
    for m in mh[d-1]:
      if i+m < h*w+1 and i+m > 0:
        if star_ck[i+m] == 1:
          #くっつけられる星座（星かも）発見！しました
          if uf.size(i+m) == 1: #くっつけ先の星が要素1しかないならとりあえずくっつける
            watacco[i+m]=0
          else:
            now="NO" #くっつけ先がすでに星座なら、増えるパターンないのでONLYを変える
            roots=uf.find(i+m) #くっつけた星座の根を記録する
            if roots not in watacco:
              watacco[roots]=0
    if now == "ONLY" and len(watacco) > 0:
      star_max=1
    else:
      star_min=max(star_min,len(watacco))
    
check=uf.all_group_members()
sign=0
for i in check:
  if len(check[i]) > 1:
    sign+=1

if sign==0:
  print(0,sign+star_max)
else:
  if star_min == 0:
    print(sign,sign+star_max)
  else:
    print(sign-star_min+1,sign+star_max)
#星がひとつのとき、新しく星座が誕生することにちゅ〜い
0