結果
問題 |
No.2946 Puyo
|
ユーザー |
|
提出日時 | 2024-10-25 21:26:25 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 287 ms / 2,000 ms |
コード長 | 2,878 bytes |
コンパイル時間 | 171 ms |
コンパイル使用メモリ | 82,848 KB |
実行使用メモリ | 123,176 KB |
最終ジャッジ日時 | 2024-10-25 21:26:44 |
合計ジャッジ時間 | 10,272 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 45 |
ソースコード
#int-input def II(): return int(input()) def MI() -> int : return map(int, input().split()) class fenwick_tree(): n=1 data=[0 for i in range(n)] def __init__(self,N): self.n=N self.data=[0 for i in range(N)] def add(self,p,x): assert 0<=p<self.n,"0<=p<n,p={0},n={1}".format(p,self.n) p+=1 while(p<=self.n): self.data[p-1]+=x p+=p& -p def sum(self,l,r): assert (0<=l and l<=r and r<=self.n),"0<=l<=r<=n,l={0},r={1},n={2}".format(l,r,self.n) return self.sum0(r)-self.sum0(l) def sum0(self,r): s=0 while(r>0): s+=self.data[r-1] r-=r&-r return s class dsu(): n=1 parent_or_size=[-1 for i in range(n)] def __init__(self,N): self.n=N self.parent_or_size=[-1 for i in range(N)] def merge(self,a,b): assert 0<=a<self.n, "0<=a<n,a={0},n={1}".format(a,self.n) assert 0<=b<self.n, "0<=b<n,b={0},n={1}".format(b,self.n) x=self.leader(a) y=self.leader(b) if x==y: return x if (-self.parent_or_size[x]<-self.parent_or_size[y]): x,y=y,x self.parent_or_size[x]+=self.parent_or_size[y] self.parent_or_size[y]=x return x def same(self,a,b): assert 0<=a<self.n, "0<=a<n,a={0},n={1}".format(a,self.n) assert 0<=b<self.n, "0<=b<n,b={0},n={1}".format(b,self.n) return self.leader(a)==self.leader(b) def leader(self,a): assert 0<=a<self.n, "0<=a<n,a={0},n={1}".format(a,self.n) if (self.parent_or_size[a]<0): return a self.parent_or_size[a]=self.leader(self.parent_or_size[a]) return self.parent_or_size[a] def size(self,a): assert 0<=a<self.n, "0<=a<n,a={0},n={1}".format(a,self.n) return -self.parent_or_size[self.leader(a)] def groups(self): leader_buf=[0 for i in range(self.n)] group_size=[0 for i in range(self.n)] for i in range(self.n): leader_buf[i]=self.leader(i) group_size[leader_buf[i]]+=1 result=[[] for i in range(self.n)] for i in range(self.n): result[leader_buf[i]].append(i) result2=[] for i in range(self.n): if len(result[i])>0: result2.append(result[i]) return result2 h,w = MI() g = [input() for i in range(h)] ans = [[""]*w for i in range(h)] uf = dsu(h*w) for i in range(h): for j in range(w): if i != h-1 and g[i][j] == g[i+1][j]: uf.merge(i*w+j,(i+1)*w+j) if j != w-1 and g[i][j] == g[i][j+1]: uf.merge(i*w+j,i*w+j+1) for i in range(h): for j in range(w): if uf.size(i*w+j) >= 4: ans[i][j] = "." else: ans[i][j] = g[i][j] for i in ans: print("".join(i))