Harryxun/GPT-100-sft-dataset huggingface dataset:
Problem p02541 (python)

Fixed submission:
from math import gcd

from collections import Counter
from itertools import product


min2 = lambda x,y: x if x < y else y


# 拡張ユークリッド互除法
# ax + by = gcd(a,b)の最小整数解を返す
def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)


# mを法とするaの乗法的逆元
def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

def chinese_remainder_theorem(R, M, prod):
    """
    returns x s.t.
    all(x%m == r for r,m in zip(R,M))
    """
    s = 0
    for m,r in zip(M,R):
        p = prod//m
        s += r * p * modinv(p,m)
        s %= prod
    return s


# 素因数分解
def prime_factors(n):
    i = 2
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            yield i
    if n > 1:
        yield n



N = int(input())

factors = Counter(prime_factors(N))
if factors[2] > 0:
    factors[2] += 1
    N *= 2
mods = [f**p for f,p in factors.items()]

res = N
for R in product(*((0,m-1) for m in mods)):
    t = chinese_remainder_theorem(R, mods, N)
    if t > 0:
        res = min2(res, t)

print(res)

Buggy submission (verdict: Runtime Error):
from math import gcd

from collections import Counter
from itertools import product


min2 = lambda x,y: x if x < y else y

def lcm(A):
    m = 1
    for a in A:
        m *= a//gcd(m,a)
    return m


def chinese_remainder_theorem(R, M):
    """
    returns x and lcm(M) s.t.
    all(x%m == r for r,m in zip(R,M))
    """
    s = 0
    big_m = lcm(M)
    for m,r in zip(M,R):
        p = big_m//m
        s += r * p * pow(p, -1, m)
        s %= big_m
    return s, big_m


# 素因数分解
def prime_factors(n):
    i = 2
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            yield i
    if n > 1:
        yield n



N = int(input())

factors = Counter(prime_factors(N))
if factors[2] > 0:
    factors[2] += 1
mods = [f**p for f,p in factors.items()]

res = N
for R in product(*((0,m-1) for m in mods)):
    t = chinese_remainder_theorem(R, mods)[0]
    if t > 0:
        res = min2(res, t)

print(res)
Problem p02560 (python)

Fixed submission:
def floor_linear_sum(n,m,a,b):
    res = 0
    while True:
        if a >= m:
            res += (n-1)*n*(a//m)//2
            a %= m
        if b >= m:
            res += n * (b//m)
            b %= m

        y_max = (a*n+b)//m
        if y_max == 0:
            return res
        x_max = y_max*m-b
        res += (n - (x_max + a - 1)//a)*y_max
        n,m,a,b = y_max, a, m, (a-x_max)%a

T = int(input())
for _ in range(T):
    print(floor_linear_sum(*map(int,input().split())))

Buggy submission (verdict: Runtime Error):
def floor_linear_sum(n,m,a,b):
    """
    returns sum((a*i+b)//m for i in range(n))
    """
    res = 0
    while True:
        if a >= m:
            res += (n-1)*n*(a//m)//2
            a %= m
        if b >= m:
            res += n * (b//m)
            b %= m

        y_max = (a*n+b)//m
        if y_max == 0:
            return res
        nx_max = b - y_max*m
        res += (n + nx_max//a)*y_max
        n,m,a,b = y_max, a, m, nx_max%a

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

T = readline()
m = map(int,read().split())
for t in zip(m,m,m,m):
    print(solve(*t))
Problem p02574 (python)

Fixed submission:
from math import gcd
from functools import reduce
from collections import Counter
from itertools import chain


# 素因数分解
def prime_factors(n):
    i = 2
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            while n % i == 0:
                n //= i
            yield i
    if n > 1:
        yield n


def solve(A):
    d = reduce(gcd, A)
    if d != 1:
        return 'not coprime'

    A.sort()

    s = set()
    for a in A:
        for p in prime_factors(a):
            if p in s:
                return 'setwise coprime'
            else:
                s.add(p)

    return 'pairwise coprime'


if __name__ == '__main__':
    N = int(input())
    A = list(map(int,input().split()))

    print(solve(A))

Buggy submission (verdict: Runtime Error):
from math import gcd
from functools import reduce
from collections import Counter
from itertools import chain


# 素因数分解
def prime_factors(n):
    i = 2
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            yield i
    if n > 1:
        yield n


def solve(A):
    d = reduce(gcd, A)
    if d != 1:
        return 'not coprime'

    c = Counter(chain.from_iterable(set(prime_factors(a)) for a in A))
    if max(c.values()) > 1:
        return 'setwise prime'
    else:
        return 'pairwise prime'


if __name__ == '__main__':
    N = int(input())
    A = list(map(int,input().split()))

    print(solve(A))
Problem p02603 (python)

Fixed submission:
N = int(input())
A = list(map(int,input().split()))

A = [A[0]] + [b for a,b in zip(A,A[1:]) if a != b]

if len(A) < 2:
    print(1000)
    exit()

diff = [a-b for a,b in zip(A[1:],A)]
B = [A[0]] if diff[0] > 0 else []

for i,(d1,d2) in enumerate(zip(diff, diff[1:]),start=1):
    if d1*d2 < 0:
        B.append(A[i])
B.append(A[-1])
t = iter(B)
c = 1000
for a,b in zip(t,t):
    c = c//a*b + c%a

print(c)

Buggy submission (verdict: Runtime Error):
N = int(input())
A = list(map(int,input().split()))

A = [A[0]] + [b for a,b in zip(A,A[1:]) if a != b]

diff = [a-b for a,b in zip(A[1:],A)]
B = [A[0]] if diff[0] > 0 else []

for i,(d1,d2) in enumerate(zip(diff, diff[1:]),start=1):
    if d1*d2 < 0:
        B.append(A[i])
B.append(A[-1])
t = iter(B)
c = 1000
for a,b in zip(t,t):
    c = c//a*b + c%a

print(c)

Buggy submission (verdict: Runtime Error):
N = int(input())
A = list(map(int,input().split()))

A = [A[0]] + [b for a,b in zip(A,A[1:]) if a != b]

diff = [a-b for a,b in zip(A[1:],A)]
B = [A[0]] if diff[0] > 0 else []

for i,(d1,d2) in enumerate(zip(diff, diff[1:]),start=1):
    if d1*d2 < 0:
        B.append(A[i])
B.append(A[-1])
t = iter(B)
c = 1000
for a,b in zip(t,t):
    c = c//a*b + c%a

print(c)
Problem p02616 (python)

Fixed submission:
from functools import reduce
import operator
MOD = 10**9+7
mprod = lambda it: reduce(lambda x,y: (x*y)%MOD,it,1)
nprod = lambda it: reduce(lambda x,y: (x*y),it,1)


from fractions import Fraction

def solve(A,K):
    N = len(A)
    if N == K:
        return mprod(A)

    if all(v <= 0 for v in A) and K%2 == 1:
        A.sort()
        return mprod(A[-K:])

    A.sort(key=lambda x: abs(x))

    if A[-K] == 0:
        return 0

    parity = sum(v < 0 for v in A[-K:])%2
    if parity == 0:
        return mprod(A[-K:])

    rp = N-K
    while rp < N and A[rp] < 0:
        rp += 1

    rn = N-K
    while rn < N and A[rn] > 0:
        rn += 1


    lp = N-K-1
    while lp >= 0 and A[lp] < 0:
        lp -= 1

    ln = N-K-1
    while ln >= 0 and A[ln] > 0:
        ln -= 1

    if rp < N and ln >= 0:
        r1 = Fraction(-A[ln],A[rp])
    else:
        r1 = 0
    if rn < N and lp >= 0:
        r2 = Fraction(-A[lp],A[rn])
    else:
        r2 = 0
    if r1 > r2:
        return (mprod(A[-K:])*A[ln]*pow(A[rp],-1,MOD))%MOD
    else:
        return (mprod(A[-K:])*A[lp]*pow(A[rn],-1,MOD))%MOD

from itertools import combinations
def naive(A,K):
    return max(nprod(p) for p in combinations(A,K))%MOD


if __name__ == '__main__':
    N,K = map(int,input().split())
    A = list(map(int,input().split()))
    
    print(solve(A,K)%MOD)

    # from random import randrange

    # N = 9
    # K = 8
    # for _ in range(100000):
    #     A = [randrange(-8,8) for _ in range(N)]
    #     if solve(A.copy(),K) != naive(A.copy(), K):
    #         print(A, solve(A.copy(),K),naive(A.copy(), K) )

Buggy submission (verdict: Runtime Error):
from functools import reduce
import operator
MOD = 10**9+7
product = lambda it: reduce(lambda x,y: (x*y)%MOD,it,1)

N,K = map(int,input().split())
A = list(map(int,input().split()))

from fractions import Fraction

def solve():
    if N == K:
        return product(A)

    if all(v < 0 for v in A):
        A.sort()
        return product(A[-K:])

    A.sort(key=lambda x: abs(x))

    if A[-K] == 0:
        return 0

    parity = sum(v < 0 for v in A[-K:])%2
    if parity == 0:
        return product(A[-K:])

    fp = N-K
    while fp < N and A[fp] < 0:
        fp += 1

    fn = N-K
    while fn < N and A[fn] > 0:
        fn += 1


    lp = N-K-1
    while lp >= 0 and A[lp] < 0:
        lp -= 1

    ln = N-K-1
    while ln >= 0 and A[ln] > 0:
        ln -= 1

    if fp < N and ln >= 0:
        r1 = Fraction(-A[ln],A[fp])
    else:
        r1 = 0
    if fn < N and lp >= 0:
        r2 = Fraction(-A[lp],A[fn])
    else:
        r2 = 0
    if r1 > r2:
        return (product(A[-K:])*A[ln]*pow(A[fp],-1,MOD))%MOD
    else:
        return (product(A[-K:])*A[lp]*pow(A[fn],-1,MOD))%MOD

print(solve())
Problem p02698 (python)

Fixed submission:
from bisect import bisect
from sys import setrecursionlimit

setrecursionlimit(10000000)

N = int(input())
A = tuple(map(int,input().split()))
adj = [list() for _ in range(N)]
for _ in range(N-1):
    a,b = map(int,input().split())
    a,b = a-1,b-1
    adj[a].append(b)
    adj[b].append(a)


res = [None]*N
dp = [float('inf') for _ in range(N)]

def rec(v, ml):
    """
    dp[l]: min tail value of increasing subsequence of length l+1
    """
    a = A[v]
    i = bisect(dp, a-1)
    ml += int(ml == i)
    res[v] = ml

    orig = dp[i]
    dp[i] = a
    for u in adj[v]:
        if res[u] is None:
            rec(u, ml)
    dp[i] = orig

rec(0, 0)

print(*res, sep='\n')

Buggy submission (verdict: Runtime Error):
from bisect import bisect


N = int(input())
A = tuple(map(int,input().split()))
adj = [list() for _ in range(N)]
for _ in range(N-1):
    a,b = map(int,input().split())
    a,b = a-1,b-1
    adj[a].append(b)
    adj[b].append(a)


res = [None]*N
dp = [float('inf') for _ in range(N)]

def rec(v, ml):
    """
    dp[l]: min tail value of increasing subsequence of length l+1
    """
    a = A[v]
    i = bisect(dp, a)
    ml += int(ml == i)
    res[v] = ml

    orig = dp[i]
    dp[i] = a
    for u in adj[v]:
        if res[u] is None:
            rec(u, ml)
    dp[i] = orig

rec(0, 0)

print(*res, sep='\n')
Problem p02705 (python)

Fixed submission:
import math
R = int(input())

print(R*2*math.pi)

Buggy submission (verdict: Runtime Error):
from collections import Counter

N = int(input())
C = tuple(map(lambda x: int(x)-1,input().split()))

adj = [list() for _ in range(N)]
for _ in range(N-1):
    a,b = map(int,input().split())
    adj[a-1].append(b-1)
    adj[b-1].append(a-1)


parent = [None]*N
parent[0] = -1

stack = [0]
order = []
while stack:
    p = stack.pop()
    order.append(p)
    for c in adj[p]:
        if parent[c] is None:
            parent[c] = p
            stack.append(c)

dp = [Counter() for _ in range(N)] # color-wise counter
subtreesize = [0]*N
cnt = [N*(N+1)//2]*N

for c in reversed(order):
    p = parent[c]
    if p >= 0:
        dp[c][C[c]] = subtreesize[c]+1
        x = subtreesize[c]-dp[c][C[p]]+1
        cnt[C[p]] -= x*(x+1)//2
        subtreesize[p] += subtreesize[c]+1

        a,b = dp[p],dp[c]
        if len(a) > len(b):
            a += b
            dp[p] = a
        else:
            b += a
            dp[p] = b
        dp[c] = None

dp[0][C[0]] = subtreesize[0]+1
for c in range(N):
    x = subtreesize[0]-dp[0][c]+1
    cnt[c] -= x*(x+1)//2

print(*cnt, sep='\n')
Problem p02720 (python)

Fixed submission:
K = int(input())

N = [0]

for _ in range(K):
    i = 0
    while i < len(N) and N[i] == 9:
        i += 1
    while i+1 < len(N) and N[i] == N[i+1]+1:
        i += 1
    if i == len(N):
        N = [0]*len(N) + [1]
    else:
        N[i] += 1
        i -= 1
        while i >= 0:
            N[i] = max(N[i+1]-1,0)
            i -= 1

print(*reversed(N),sep='')

Buggy submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline

def binary_search_int(ok, ng, solve):
    """
    :param ok: solve(x) = True を必ず満たす点
    :param ng: solve(x) = False を必ず満たす点
    """
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if solve(mid):
            ok = mid
        else:
            ng = mid
    return ok, ng

##############################################################

def solve(x):
    """ ある点 x を境にして True と False が二分されるような関数"""
    return N - K*x >= 0

N, K = map(int, input().split())

a, b = binary_search_int(0, 10**18, solve)
print(min(abs(N-a*K), abs(N-b*K)))
Problem p02805 (python)

Fixed submission:
import numpy as np
from itertools import combinations

N = int(input())

P = [np.array(list(map(int,input().split())), dtype=float) for _ in range(N)]

d2 = lambda v: np.sum(np.square(v))

def radius(A,B,C):
    a = d2(B-C)
    b = d2(C-A)
    c = d2(A-B)

    r = float('inf')
    if c > d2(A+B - 2*C):
        r = min(r, c)

    if a > d2(B+C - 2*A):
        r = min(r, a)

    if b > d2(C+A - 2*B):
        r = min(r, b)

    if r != float('inf'):
        return np.sqrt(r)/2

    U = a*(b+c-a)*A + b*(c+a-b)*B + c*(a+b-c)*C
    v = a*(b+c-a) + b*(c+a-b) + c*(a+b-c)
    U /= v
    r = np.linalg.norm(U-A)
    return r

if N == 2:
    print(np.linalg.norm(P[0]-P[1])/2)
else:
    print(max(radius(a,b,c) for a,b,c in combinations(P,3)))

Buggy submission (verdict: Runtime Error):
import numpy as np
from math import sqrt
from itertools import combinations

N = int(input())

P = [np.array(list(map(int,input().split())), dtype=np.int64) for _ in range(N)]

d2 = lambda v: v.dot(v)

def radius(A,B,C):
    a = d2(B-C)
    b = d2(C-A)
    c = d2(A-B)

    r = float('inf')
    if c > d2(A+B - 2*C):
        r = min(r, c)

    if a > d2(B+C - 2*A):
        r = min(r, a)

    if b > d2(C+A - 2*B):
        r = min(r, b)

    if r != float('inf'):
        return sqrt(float(r))/2

    U = a*(b+c-a)*A + b*(c+a-b)*B + c*(a+b-c)*C
    v = a*(b+c-a) + b*(c+a-b) + c*(a+b-c)
    return sqrt(float(d2(U-v*A)))/v

if N == 2:
    print(sqrt(float(d2(P[0]-P[1])))/2)
else:
    print(max(radius(a,b,c) for a,b,c in combinations(P,3)))
Problem p02824 (python)

Fixed submission:
from bisect import bisect as list_bisect
max2 = lambda x,y: x if x > y else y
min2 = lambda x,y: x if x < y else y

def bisect(ng, ok, judge, eps=1):
    while abs(ng-ok) > eps:
        m = (ng+ok)//2
        if judge(m):
            ok = m
        else:
            ng = m
    return ok

N,M,V,P = map(int,input().split())
A = sorted(map(int,input().split()))

k = N-P
def judge(i):
    if i >= k:
        return True
    a = A[i]
    if a+M < A[k]:
        return False

    r = 0
    for v in A[i+1:k+1]:
        r += a+M-v
    return r >= (V-P-i)*M

i = bisect(-1,N-1,judge)
print(N-i)

Buggy submission (verdict: Runtime Error):
from bisect import bisect as list_bisect
max2 = lambda x,y: x if x > y else y
min2 = lambda x,y: x if x < y else y

def bisect(ng, ok, judge, eps=1):
    while abs(ng-ok) > eps:
        m = (ng+ok)//2
        if judge(m):
            ok = m
        else:
            ng = m
    return ok

N,M,V,P = map(int,input().split())
A = sorted(map(int,input().split()))
def judge(i):
    if len(A) <= P:
        return True
    a = A[i]
    if V <= P:
        return a+M >= A[-P]
    k = max2(0,V-P+1-i)
    if k-P >= 0:
        return False
    else:
        return a+M > A[-P+k]

i = bisect(-1,N-1,judge)
x = A[i]
while A[i-1] == x:
    i -= 1
print(N-i)
Problem p02839 (python)

Fixed submission:
import numpy as np

H,W = map(int,input().split())

A = np.array(tuple(tuple(map(int,input().split())) for _ in range(H)))
B = np.array(tuple(tuple(map(int,input().split())) for _ in range(H)))

D = np.abs(A-B)
del A,B

if W > H:
    W,H = H,W
    D = D.T

L = D.max()*(H+W-1)+1
dp0 = np.zeros((W,L), dtype=bool)
dp1 = np.zeros_like(dp0)

dp1[0,D[0,0]] = True
for y in range(H):
    for x in range(W):
        d = D[y,x]

        dp1[x,d:] |= dp0[x,:L-d]
        dp1[x,:L-d] |= dp0[x,d:]
        dp1[x,:d] |= dp0[x,d:0:-1]
        dp1[x,d:] |= dp1[x-1,:L-d]
        dp1[x,:L-d] |= dp1[x-1,d:]
        dp1[x,:d] |= dp1[x-1,d:0:-1]
    dp0,dp1 = dp1, np.zeros_like(dp1)

print(min(i for i,v in enumerate(dp0[-1]) if v))

Buggy submission (verdict: Runtime Error):
from itertools import chain

H,W = map(int,input().split())

A = tuple(tuple(map(int,input().split())) for _ in range(H))
B = tuple(tuple(map(int,input().split())) for _ in range(H))

dp = {(0,0) : {(A[0][0]-B[0][0])%160, (B[0][0]-A[0][0])%160}}


for t in range(1,H+W-1):
    ndp = dict()
    for x in range(max(0,t-H+1), min(t+1,W)):
        y = t-x
        d = A[y][x]-B[y][x]
        if x > 0 and y > 0:
            ns = set(k%160 for k in chain((v+d for v in dp[(x-1,y)]),
                            (v-d for v in dp[(x-1,y)]),
                            (v+d for v in dp[(x,y-1)]),
                            (v-d for v in dp[(x,y-1)]),))
        elif x > 0:
            ns = set(k%160 for k in chain((v+d for v in dp[(x-1,y)]),
                            (v-d for v in dp[(x-1,y)]),))
        elif y > 0:
            ns = set(k%160 for k in chain((v+d for v in dp[(x,y-1)]),
                            (v-d for v in dp[(x,y-1)]),))
        else:
            ns = set()

        ndp[(x,y)] = ns
    dp = ndp

print(min(dp[(W-1,H-1)], (160-v for v in dp[(W-1,H-1)] ))
Problem p02843 (python)

Fixed submission:
from functools import lru_cache
import sys

sys.setrecursionlimit(1000000)

X = int(input())

@lru_cache(None)
def rec(x):
    if x == 0:
        return True
    if x < 0:
        return False
    return any(rec(x-100-d) for d in range(6))

print(1 if rec(X) else 0)

Buggy submission (verdict: Runtime Error):
from functools import lru_cache

X = int(input())

@lru_cache(None)
def rec(x):
    if x == 0:
        return True
    if x < 0:
        return False
    return any(rec(x-100-d) for d in range(6))

print(1 if rec(X) else 0)
Problem p02913 (python)

Fixed submission:
from itertools import accumulate
max2 = lambda x,y: x if x > y else y
min2 = lambda x,y: x if x < y else y

N = int(input())
S = input()

res = 0
for i in range(1,N):
    m = 0
    r = 0
    for a,b in zip(S,S[i:]):
        if a == b:
            r += 1
        else:
            r = 0
        m = max2(m,r)
    m = min2(m,i)
    res = max2(res, m)

print(res)

Buggy submission (verdict: Runtime Error):
N = int(input())
S = input()

for l in reversed(range(1,N//2+1)):
    for i in range(N-2*l+1):
        for j in range(i+l,N-l+1):
            print(S[i:i+l],S[j:j+l])
            if S[i:i+l] == S[j:j+l]:
                print(l)
                exit()

print(0)
Problem p02921 (python)

Fixed submission:
S,T = input(),input()

print(sum(int(a==b) for a,b in zip(S,T)))

Buggy submission (verdict: Runtime Error):
S,T = input(),input()

print(sum(int(a==b) for a,b zip(S,T)))
Problem p02936 (python)

Fixed submission:
N,Q = map(int,input().split())

adj = [list() for _ in range(N)]
for _ in range(N-1):
    a,b = map(int,input().split())
    adj[a-1].append(b-1)

memo = [0]*N
for _ in range(Q):
    p,x = map(int,input().split())
    memo[p-1] += x

result = [None]*N
stack = [(0,0)]
while stack:
    v,a = stack.pop()
    a += memo[v]
    result[v] = a
    for u in adj[v]:
        stack.append((u,a))

print(*result)

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(100000)

N,Q = map(int,input().split())

adj = [list() for _ in range(N)]
for _ in range(N-1):
    a,b = map(int,input().split())
    adj[a-1].append(b-1)
memo = [0]*N
for _ in range(Q):
    p,x = map(int,input().split())
    memo[p-1] += x

result = [None]*N
def dfs(v,a):
    c = memo[v]
    for u in adj[v]:
        dfs(u,a+c)
    result[v] = a+c
dfs(0,0)
print(*result)

Buggy submission (verdict: Runtime Error):
N,Q = map(int,input().split())

adj = [list() for _ in range(N)]
for _ in range(N-1):
    a,b = map(int,input().split())
    adj[a-1].append(b-1)
memo = [0]*N
for _ in range(Q):
    p,x = map(int,input().split())
    memo[p-1] += x

result = [None]*N
def dfs(v,a):
    c = memo[v]
    for u in adj[v]:
        dfs(u,a+c)
    result[v] = a+c
dfs(0,0)
print(*result)
Problem p02949 (python)

Fixed submission:
N,M,P = map(int,input().split())

adj = [list() for _ in range(N)]
inv = [list() for _ in range(N)]
edges = []

for _ in range(M):
    a,b,c = map(int,input().split())
    inv[b-1].append(a-1)
    adj[a-1].append(b-1)
    edges.append((a-1,b-1,P-c))

stack = [N-1]
reachable1 = {N-1}
while stack:
    v = stack.pop()
    for u in inv[v]:
        if u not in reachable1:
            stack.append(u)
            reachable1.add(u)

stack = [0]
reachable2 = {0}
while stack:
    v = stack.pop()
    for u in adj[v]:
        if u not in reachable2:
            stack.append(u)
            reachable2.add(u)

reachable = reachable1 & reachable2
edges = [(a,b,w) for a,b,w in edges if a in reachable and b in reachable]

dist = [float('inf')]*N
dist[0] = 0

for i in range(len(reachable)-1):
    for a,b,w in edges:
        dist[b] = min(dist[a]+w, dist[b])

# negative cycle
for a,b,w in edges:
    if dist[b] > dist[a] + w:
        print(-1)
        break
else:
    print(max(0,-dist[-1]))

Buggy submission (verdict: Runtime Error):
from scipy.sparse.csgraph import bellman_ford, NegativeCycleError
from scipy.sparse import dok_matrix
from math import ceil

N,M,P = map(int,input().split())

adj = [list() for _ in range(N)]
inv = [list() for _ in range(N)]
edges = []

for _ in range(M):
    a,b,c = map(int,input().split())
    inv[b-1].append(a-1)
    adj[a-1].append(b-1)
    edges.append((a-1,b-1,P-c))

stack = [N-1]
reachable1 = {N-1}
while stack:
    v = stack.pop()
    for u in inv[v]:
        if u not in reachable1:
            stack.append(u)
            reachable1.add(u)

stack = [0]
reachable2 = {0}
while stack:
    v = stack.pop()
    for u in adj[v]:
        if u not in reachable2:
            stack.append(u)
            reachable2.add(u)

reachable = reachable1 & reachable2
edges = [(a,b,w) for a,b,w in edges if a in reachable and b in reachable]

dist = [float('inf')]*N
dist[0] = 0

for i in range(len(reachable)-1):
    for a,b,w in edges:
        dist[b] = min(dist[a]+w, dist[b])

# negative cycle
for a,b,w in edges:
    if dist[b] > dist[a] + w:
        print(-1)
        break
else:
    print(max(0,-dist[-1]))

Buggy submission (verdict: Runtime Error):
from scipy.sparse.csgraph import bellman_ford, NegativeCycleError
from scipy.sparse import dok_matrix

N,M,P = map(int,input().split())

adj = [list() for _ in range(N)]
reachable = {N-1}


for _ in range(M):
    a,b,c = map(int,input().split())
    adj[b-1].append((a-1,c))
stack = [N-1]
while stack:
    v = stack.pop()
    for u,_ in adj[v]:
        if u not in reachable:
            stack.append(u)
            reachable.add(u)

G = dok_matrix((N,N))
for u,l in enumerate(adj):
    if u not in reachable:
        continue
    for v,c in l:
        if v not in reachable:
            continue
        w = -c+P
        w = 0.00000001 if w == 0 else w
        G[v,u] = w
try:
    D = bellman_ford(G, indices=0)
    print(max(0, int(-D[-1])))
except NegativeCycleError:
    print(-1)