結果

問題 No.1502 Many Simple Additions
ユーザー aaaaaaaaaa2230aaaaaaaaaa2230
提出日時 2021-05-08 13:56:16
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 572 ms / 2,000 ms
コード長 2,590 bytes
コンパイル時間 243 ms
コンパイル使用メモリ 86,412 KB
実行使用メモリ 134,536 KB
最終ジャッジ日時 2023-10-15 00:38:31
合計ジャッジ時間 11,935 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 92 ms
71,460 KB
testcase_01 AC 90 ms
71,088 KB
testcase_02 AC 88 ms
71,088 KB
testcase_03 AC 88 ms
71,084 KB
testcase_04 AC 88 ms
70,912 KB
testcase_05 AC 87 ms
71,084 KB
testcase_06 AC 88 ms
71,080 KB
testcase_07 AC 89 ms
71,396 KB
testcase_08 AC 89 ms
71,388 KB
testcase_09 AC 90 ms
71,356 KB
testcase_10 AC 89 ms
71,264 KB
testcase_11 AC 86 ms
71,172 KB
testcase_12 AC 89 ms
71,264 KB
testcase_13 AC 88 ms
71,396 KB
testcase_14 AC 89 ms
71,088 KB
testcase_15 AC 89 ms
71,468 KB
testcase_16 AC 89 ms
71,400 KB
testcase_17 AC 92 ms
71,268 KB
testcase_18 AC 93 ms
71,204 KB
testcase_19 AC 91 ms
71,240 KB
testcase_20 AC 92 ms
71,548 KB
testcase_21 AC 91 ms
71,420 KB
testcase_22 AC 89 ms
71,404 KB
testcase_23 AC 90 ms
70,912 KB
testcase_24 AC 88 ms
71,264 KB
testcase_25 AC 87 ms
71,476 KB
testcase_26 AC 90 ms
71,264 KB
testcase_27 AC 342 ms
128,256 KB
testcase_28 AC 303 ms
127,724 KB
testcase_29 AC 230 ms
116,372 KB
testcase_30 AC 572 ms
134,532 KB
testcase_31 AC 502 ms
127,928 KB
testcase_32 AC 525 ms
134,536 KB
testcase_33 AC 324 ms
95,952 KB
testcase_34 AC 308 ms
95,596 KB
testcase_35 AC 326 ms
96,572 KB
testcase_36 AC 196 ms
84,640 KB
testcase_37 AC 199 ms
84,848 KB
testcase_38 AC 251 ms
88,956 KB
testcase_39 AC 187 ms
83,020 KB
testcase_40 AC 292 ms
99,096 KB
testcase_41 AC 200 ms
89,896 KB
testcase_42 AC 485 ms
123,192 KB
testcase_43 AC 90 ms
71,408 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import deque
n,m,k = map(int,input().split())
mod = 10**9+7
inf = 10**10
e = [[] for i in range(n)]
for i in range(m):
    x,y,z = map(int,input().split())
    x -= 1
    y -= 1
    e[x].append((y,z))
    e[y].append((x,z))
    
def calc(k):
    use = [0]*n
    dis = [-1]*n
    val = [[-1]*2 for i in range(n)]
    def bimatch(x,k):
        bians = None
        dis[x] = 0
        val[x] = [1,0]
        use[x] = 1
        vis = []
        q = deque([x])
        while q:
            now = q.popleft()
            vis.append(now)
            a,b = val[now]
            for nex,c in e[now]:
                if dis[nex] == -1:
                    dis[nex] = dis[now]^1
                    val[nex] = [-a,c-b]
                    q.append(nex)
                    use[nex] = 1
                else:
                    na,nb = val[nex]
                    if a+na == 0:
                        if  b+nb != c:
                            return 0
                    
                    else:
                        if (c-b-nb)%(a+na):
                            return 0
                        if bians == None:
                            bians = (c-b-nb)//(a+na)
                        else:
                            if bians != (c-b-nb)//(a+na):
                                return 0
                        
        if bians != None:
            for v in vis:
                a,b = val[v]
                num = bians*a+b
                if num < 1 or num > k:
                    return 0
            return 1

        odd = [inf,-inf]
        even = [inf,-inf]
        for v in vis:
            a,b = val[v]
            if dis[v]%2:
                odd[0] = min(odd[0],a+b)
                odd[1] = max(odd[1],a+b)
            else:
                even[0] = min(even[0],a+b)
                even[1] = max(even[1],a+b)
 
        if odd[0] == inf:
            return k
        if odd[0] > even[0]:
            odd,even = even,odd
        if odd[0] < 1:
            dif = 1-odd[0]
            odd = [odd[0]+dif,odd[1]+dif]
            even = [even[0]-dif,even[1]-dif]
        if even[1] > k:
            dif = even[1]-k
            odd = [odd[0]+dif,odd[1]+dif]
            even = [even[0]-dif,even[1]-dif]
        
        if odd[0] < 1 or odd[1] > k or even[0] < 1 or even[1] > k:
            return 0
        count = min(k-odd[1],even[0]-1)+min(k-even[1],odd[0]-1)+1

        return count

    ans = 1
    for i in range(n):
        if use[i]:
            continue
        ans *= bimatch(i,k)
        ans %= mod
    return ans

print((calc(k)-calc(k-1))%mod)
0