結果

問題 No.1502 Many Simple Additions
ユーザー aaaaaaaaaa2230
提出日時 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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 39
権限があれば一括ダウンロードができます

ソースコード

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