結果

問題 No.1303 Inconvenient Kingdom
ユーザー chineristACchineristAC
提出日時 2020-11-27 23:16:15
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,149 bytes
コンパイル時間 277 ms
コンパイル使用メモリ 87,184 KB
実行使用メモリ 79,044 KB
最終ジャッジ日時 2023-10-09 21:07:30
合計ジャッジ時間 4,970 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 62 ms
71,112 KB
testcase_01 AC 64 ms
71,468 KB
testcase_02 WA -
testcase_03 AC 61 ms
71,172 KB
testcase_04 AC 76 ms
76,060 KB
testcase_05 AC 75 ms
76,196 KB
testcase_06 AC 81 ms
76,412 KB
testcase_07 AC 87 ms
76,452 KB
testcase_08 AC 86 ms
76,668 KB
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 AC 125 ms
78,852 KB
testcase_27 AC 115 ms
78,904 KB
testcase_28 AC 120 ms
79,044 KB
testcase_29 AC 68 ms
75,984 KB
testcase_30 AC 72 ms
76,136 KB
testcase_31 AC 73 ms
75,832 KB
testcase_32 AC 71 ms
76,084 KB
testcase_33 AC 75 ms
76,180 KB
testcase_34 AC 63 ms
71,492 KB
testcase_35 WA -
testcase_36 AC 73 ms
76,064 KB
testcase_37 AC 72 ms
76,064 KB
権限があれば一括ダウンロードができます

ソースコード

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)
0