結果

問題 No.1502 Many Simple Additions
ユーザー aaaaaaaaaa2230aaaaaaaaaa2230
提出日時 2021-05-08 13:56:16
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 579 ms / 2,000 ms
コード長 2,590 bytes
コンパイル時間 278 ms
コンパイル使用メモリ 82,576 KB
実行使用メモリ 133,188 KB
最終ジャッジ日時 2024-09-16 18:11:43
合計ジャッジ時間 10,412 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge6
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 43 ms
55,256 KB
testcase_01 AC 43 ms
55,304 KB
testcase_02 AC 43 ms
55,316 KB
testcase_03 AC 45 ms
54,880 KB
testcase_04 AC 43 ms
55,976 KB
testcase_05 AC 44 ms
55,044 KB
testcase_06 AC 43 ms
54,644 KB
testcase_07 AC 44 ms
54,900 KB
testcase_08 AC 44 ms
55,184 KB
testcase_09 AC 42 ms
55,228 KB
testcase_10 AC 43 ms
55,412 KB
testcase_11 AC 43 ms
54,568 KB
testcase_12 AC 43 ms
54,944 KB
testcase_13 AC 43 ms
54,844 KB
testcase_14 AC 43 ms
54,852 KB
testcase_15 AC 43 ms
54,432 KB
testcase_16 AC 45 ms
54,640 KB
testcase_17 AC 47 ms
55,948 KB
testcase_18 AC 47 ms
56,212 KB
testcase_19 AC 45 ms
56,164 KB
testcase_20 AC 45 ms
55,720 KB
testcase_21 AC 45 ms
55,720 KB
testcase_22 AC 45 ms
55,108 KB
testcase_23 AC 44 ms
55,856 KB
testcase_24 AC 44 ms
55,568 KB
testcase_25 AC 43 ms
54,852 KB
testcase_26 AC 46 ms
55,472 KB
testcase_27 AC 291 ms
127,540 KB
testcase_28 AC 284 ms
128,192 KB
testcase_29 AC 204 ms
115,800 KB
testcase_30 AC 574 ms
133,188 KB
testcase_31 AC 562 ms
131,512 KB
testcase_32 AC 579 ms
128,492 KB
testcase_33 AC 342 ms
95,744 KB
testcase_34 AC 330 ms
98,340 KB
testcase_35 AC 348 ms
96,180 KB
testcase_36 AC 166 ms
83,376 KB
testcase_37 AC 164 ms
83,456 KB
testcase_38 AC 246 ms
89,512 KB
testcase_39 AC 151 ms
81,624 KB
testcase_40 AC 289 ms
98,368 KB
testcase_41 AC 171 ms
87,884 KB
testcase_42 AC 536 ms
122,132 KB
testcase_43 AC 43 ms
54,632 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