結果

問題 No.2884 Pieces on Squares
コンテスト
ユーザー あじゃじゃ
提出日時 2025-01-14 03:56:06
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 659 ms / 2,000 ms
コード長 1,645 bytes
コンパイル時間 550 ms
コンパイル使用メモリ 82,540 KB
実行使用メモリ 78,244 KB
最終ジャッジ日時 2025-01-14 03:56:26
合計ジャッジ時間 13,486 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 45
権限があれば一括ダウンロードができます

ソースコード

diff # 

class dsu:
    def __init__(self,n):
        self.n=n
        self.groupsize=[1 for _ in range(self.n)]
        self.root=[i for i in range(self.n)]
    def leader(self,target):
        if self.root[target]==target:
            return target
        self.root[target]=self.leader(self.root[target])#経路圧縮
        return self.root[target]
    def merge(self,u,v):
        u=self.leader(u)
        v=self.leader(v)
        if u==v:
            return u
        if self.groupsize[v]>self.groupsize[u]:#マージテク
            u,v=v,u
        self.root[v]=u
        self.groupsize[u]+=self.groupsize[v]
        return self.root[v]
    def same(self,u,v):
        return self.leader(u)==self.leader(v)
    def size(self,u):
        return self.groupsize[self.leader(u)]

h,w,n=map(int,input().split())
uf=dsu(h+w)
for i in range(n):
    a,b=map(int,input().split())
    a-=1
    b-=1
    uf.merge(a,b+h)
gg=[[] for _ in range(h+w)]
gcnt=0
for i in range(h+w):
    gg[uf.leader(i)].append(i)
    if gg[uf.leader(i)]==1:
        gcnt+=1
tg=[]
for i in range(h+w):
    if len(gg[i]):
        tg.append(gg[i])
inf=1<<60
dp_mn=[inf for _ in range(h+1)]
dp_mx=[-inf for _ in range(h+1)]
dp_mn[0],dp_mx[0]=0,0
gcnt=len(tg)
for i in range(gcnt):
    rc,cc=0,0
    for j in tg[i]:
        if j<h:
            rc+=1
        else:
            cc+=1
    for k in range(h,-1,-1):
        if dp_mn[k]!=inf:
            dp_mn[k+rc]=min(dp_mn[k+rc],dp_mn[k]+cc)
            dp_mx[k+rc]=max(dp_mx[k+rc],dp_mx[k]+cc)
ans=0
for i in range(h+1):
    if dp_mn[i]!=inf:
        ans=max(ans,i*(w-dp_mn[i])+(h-i)*dp_mn[i],i*(w-dp_mx[i])+(h-i)*dp_mx[i])
print(ans)
0