結果

問題 No.1303 Inconvenient Kingdom
ユーザー chineristAC
提出日時 2020-11-27 23:16:15
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,149 bytes
コンパイル時間 391 ms
コンパイル使用メモリ 82,216 KB
実行使用メモリ 78,004 KB
最終ジャッジ日時 2024-07-26 19:33:40
合計ジャッジ時間 4,003 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3 WA * 1
other AC * 16 WA * 18
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

def det(G, mod):
    N = len(G)
    res = 1
    for i in range(N):
        for h in range(i, N):
            if G[h][i]:
                break
        if i != h:
            G[i], G[h] = G[h][:], G[i][:]
        gii = G[i][i]
        res = res*gii%mod
        giiv = pow(gii, mod-2, mod)
        for w in range(i, N):
            G[i][w] = G[i][w]*giiv%mod
        for j in range(i+1, N):
            gji = G[j][i]
            if gji:
                for w in range(i, N):
                    G[j][w] = (G[j][w]-gji*G[i][w])%mod
    return res
class UnionFindVerSize():
    def __init__(self, N):
        self._parent = [n for n in range(0, N)]
        self._size = [1] * N
        self.group = N
    def find_root(self, x):
        if self._parent[x] == x: return x
        self._parent[x] = self.find_root(self._parent[x])
        stack = [x]
        while self._parent[stack[-1]]!=stack[-1]:
            stack.append(self._parent[stack[-1]])
        for v in stack:
            self._parent[v] = stack[-1]
        return self._parent[x]
    def unite(self, x, y):
        gx = self.find_root(x)
        gy = self.find_root(y)
        if gx == gy: return
        self.group -= 1
        if self._size[gx] < self._size[gy]:
            self._parent[gx] = gy
            self._size[gy] += self._size[gx]
        else:
            self._parent[gy] = gx
            self._size[gx] += self._size[gy]
    def get_size(self, x):
        return self._size[self.find_root(x)]
    def is_same_group(self, x, y):
        return self.find_root(x) == self.find_root(y)
N,M = map(int,input().split())
edge = [tuple(map(lambda x:int(x)-1,input().split())) for i in range(M)]
uf = UnionFindVerSize(N)
for u,v in edge:
    uf.unite(u,v)
V = [[] for i in range(N)]
E = [[] for i in range(N)]
for v in range(N):
    V[uf.find_root(v)].append(v)
for u,v in edge:
    E[uf.find_root(u)].append((u,v))
#print(V)
#print(E)
if uf.group!=1:
    res = 1
    mod = 998244353
    for root in range(N):
        if V[root]:
            idx = {e:i for i,e in enumerate(V[root])}
            #print(idx,root,E[root])
            G = [[0 for j in range(len(V[root]))] for i in range(len(V[root]))]
            for u,v in E[root]:
                uidx,vidx = idx[u],idx[v]
                #print(uidx,vidx)
                G[uidx][uidx] += 1
                G[vidx][vidx] += 1
                G[uidx][vidx] -= 1
                G[vidx][uidx] -= 1
            G = [[G[i][j] for j in range(1,len(V[root]))] for i in range(1,len(V[root]))]
            #print(det(G,mod))
            res *= det(G,mod)
            res %= mod
    add = 0
    M = 0
    for i in range(N):
        for j in range(i+1,N):
            v1,v2 = len(V[i]),len(V[j])
            if v1*v2==0:
                continue
            if v1*(N-v1) + v2*(N-v2) - (v1+v2)*(N-v1-v2) > M:
                M = v1*(N-v1) + v2*(N-v2) - (v1+v2)*(N-v1-v2)
                add = 0
            if v1*(N-v1) + v2*(N-v2) - (v1+v2)*(N-v1-v2) == M:
                add += v1*v2
    res *= add
    res %= mod
    mini = -M
    for i in range(N):
        mini += len(V[i]) * (N - len(V[i]))
    print(mini)
    print(res)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0