#655554 (PyPy3) No.1502 Many Simple Additions

• 問題: 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

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
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)
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX