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

Fixed submission:
import sys
sys.setrecursionlimit(10**7)

def main():
    N, M = map(int, input().split())
    V = [[] for _ in range(N)]
    for _ in range(M):
        a, b = map(int, input().split())
        V[a - 1].append(b - 1)
    C = [0] * N
    loop = []
    def dfs(n):
        if C[n] == 2:
            return False
        if C[n] == 1:
            loop.append(n)
            return True
        C[n] = 1
        for i in V[n]:
            if dfs(i):
                loop.append(n)
                return True
        C[n] = 2
        return False
    for i in range(N):
        if dfs(i):
            break
    if len(loop) == 0:
        print('-1')
        return
    for i in range(1, len(loop)):
        if loop[i] == loop[0]:
            break
    loop = loop[:i][::-1]

    def minimize(l):
        s = set(l)
        for i in range(len(l)):
            for j in V[l[i]]:
                if j == l[(i + 1) % len(l)]:
                    continue
                if j in s:
                    break
            else:
                continue
            break
        else:
            return l
        I = {m: k for k, m in enumerate(l)}
        j = I[j]
        if i < j:
            l = l[0:i + 1] + l[j:]
        else:
            l = l[j:i + 1]
        return l
    while True:
        t = len(loop)
        loop = minimize(loop)
        if len(loop) == t:
            break
    print(t)
    print('\n'.join(str(i + 1) for i in loop))
main()

Buggy submission (verdict: Runtime Error):
def main():
    N, M = map(int, input().split())
    V = [[] for _ in range(N)]
    for _ in range(M):
        a, b = map(int, input().split())
        V[a - 1].append(b - 1)
    C = [0] * N
    loop = []
    def dfs(n):
        if C[n] == 2:
            return False
        if C[n] == 1:
            loop.append(n)
            return True
        C[n] = 1
        for i in V[n]:
            if dfs(i):
                loop.append(n)
                return True
        C[n] = 2
        return False
    for i in range(N):
        if dfs(i):
            break
    if len(loop) == 0:
        print('-1')
        return
    for i in range(1, len(loop)):
        if loop[i] == loop[0]:
            break
    loop = loop[:i][::-1]

    def minimize(l):
        s = set(l)
        for i in range(len(l)):
            for j in V[l[i]]:
                if j == l[(i + 1) % len(l)]:
                    continue
                if j in s:
                    break
            else:
                continue
            break
        else:
            return l
        I = {m: k for k, m in enumerate(l)}
        j = I[j]
        if i < j:
            l = l[0:i + 1] + l[j:]
        else:
            l = l[j:i + 1]
        return l
    while True:
        t = len(loop)
        loop = minimize(loop)
        if len(loop) == t:
            break
    print(t)
    print('\n'.join(str(i + 1) for i in loop))
main()
Problem p02936 (python)

Fixed submission:
import sys
sys.setrecursionlimit(10**7)

def main():
    N, Q = [int(i) for i in input().split()]
    V = [set() for _ in range(N)]
    for _ in range(N - 1):
        a, b = [int(i) - 1 for i in input().split()]
        V[a].add(b)
        V[b].add(a)
    C = [0] * N
    for _ in range(Q):
        p, x = [int(i) for i in input().split()]
        C[p - 1] += x
    cur = [(0, 0)]
    while cur:
        nxt = []
        for n, x in cur:
            C[n] = x = C[n] + x
            for c in V[n]:
                V[c].remove(n)
                nxt.append((c, x))
        cur = nxt
    print(' '.join(str(c) for c in C))

main()

Buggy submission (verdict: Runtime Error):
def main():
    N, Q = [int(i) for i in input().split()]
    E = [tuple(int(i) for i in input().split()) for _ in range(N - 1)]
    V = [set() for _ in range(N)]
    for a, b in E:
        V[a - 1].add(b - 1)
        V[b - 1].add(a - 1)
    O = [tuple(int(i) for i in input().split()) for _ in range(Q)]
    C = [0] * N
    for p, x in O:
        C[p - 1] += x
    def add(n, x):
        C[n] += x
        for c in V[n]:
            V[c].remove(n)
            add(c, C[n])
    add(0, 0)
    print(' '.join(str(c) for c in C))

main()
Problem p02949 (python)

Fixed submission:
from scipy.sparse import csr_matrix, lil_matrix
from scipy.sparse.csgraph import bellman_ford, NegativeCycleError


def main():
    N, M, P = map(int, input().split())
    A, B, C = [0] * M, [0] * M, [0] * M
    v = [set() for _ in range(N)]
    u = [set() for _ in range(N)]
    for i in range(M):
        a, b, c = map(int, input().split())
        A[i], B[i], C[i] = a - 1, b - 1, P - c
        u[a - 1].add(b - 1)
        v[b - 1].add(a - 1)
    vv = set()
    cur = set([N - 1])
    while cur:
        vv |= cur
        cur = set().union(*(v[c] for c in cur)) - vv
    uu = set()
    cur = set([0])
    while cur:
        uu |= cur
        cur = set().union(*(u[c] for c in cur)) - uu
    reachable = vv & uu
    l = {}
    for a, b, c in zip(A, B, C):
        if a in reachable and b in reachable:
            l[(a, b)] = min(c, l.get((a, b), 10 **9))
    AA, BB, CC = [], [], []
    for (a, b), c in l.items():
        AA.append(a)
        BB.append(b)
        CC.append(c)
    mx = csr_matrix((CC, (AA, BB)), shape=(N, N))
    try:
        dm = bellman_ford(mx, indices=[0])
    except NegativeCycleError:
        return -1
    return max(0, -int(dm[0][N - 1]))


print(main())

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


def main():
    N, M, P = map(int, input().split())
    A, B, C = [0] * M, [0] * M, [0] * M
    v = [set() for _ in range(N)]
    u = [set() for _ in range(N)]
    for i in range(M):
        a, b, c = map(int, input().split())
        A[i], B[i], C[i] = a - 1, b - 1, P - c
        u[a - 1].add(b - 1)
        v[b - 1].add(a - 1)
    vv = set()
    cur = set([N - 1])
    while cur:
        vv |= cur
        cur = set().union(*(v[c] for c in cur)) - vv
    uu = set()
    cur = set([0])
    while cur:
        uu |= cur
        cur = set().union(*(u[c] for c in cur)) - uu
    reachable = vv & uu
    for i in range(M):
        if A[i] not in reachable or B[i] not in reachable:
            C[i] = 10 ** 9

    mx = csr_matrix((C, (A, B)), shape=(M, M))
    try:
        dm = bellman_ford(mx, indices=list(reachable))
    except NegativeCycleError:
        return -1
    return max(0, -int(dm[0][N - 1]))


print(main())

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


def main():
    N, M, P = map(int, input().split())
    A, B, C = [0] * M, [0] * M, [0] * M
    for i in range(M):
        a, b, c = map(int, input().split())
        A[i], B[i], C[i] = a - 1, b - 1, P - c
    mx = csr_matrix((C, (A, B)), shape=(M, M))
    try:
        dm = bellman_ford(mx, indices=[N - 1])
    except NegativeCycleError:
        return -1
    return max(0, -int(dm[0][N - 1]))


print(main())
Problem p02985 (python)

Fixed submission:
import sys
sys.setrecursionlimit(10**6)
def main():
    N, K = map(int, input().split())
    Nodes = [set() for _ in range(N)]
    MOD = 10 ** 9 + 7
    for i in range(N - 1):
        a, b = map(int, input().split())
        Nodes[a - 1].add(b - 1)
        Nodes[b - 1].add(a - 1)
    def helper(n, k, f):
        l = len(Nodes[n])
        r = (K - k) 
        j = 1 if k == 0 else 2
        for i in Nodes[n]:
            if i == f:
                continue
            r = r * helper(i, j, n) % MOD
            j += 1
        return r
    for i in range(N):
        if len(Nodes[i]) == 1:
            break
    return helper(i, 0, -1)

print(main())

Buggy submission (verdict: Runtime Error):
def main():
    N, K = map(int, input().split())
    Nodes = [set() for _ in range(N)]
    MOD = 10 ** 9 + 7
    for i in range(N - 1):
        a, b = map(int, input().split())
        Nodes[a - 1].add(b - 1)
        Nodes[b - 1].add(a - 1)
    def helper(n, k, f):
        l = len(Nodes[n])
        r = (K - k) 
        j = 1 if k == 0 else 2
        for i in Nodes[n]:
            if i == f:
                continue
            r = r * helper(i, j, n) % MOD
            j += 1
        return r
    for i in range(N):
        if len(Nodes[i]) == 1:
            break
    return helper(i, 0, -1)

print(main())
Problem p02997 (python)

Fixed submission:
from math import factorial
from itertools import combinations, islice

def nCr(n, r):
    return factorial(n) // factorial(r) // factorial(n - r)

def main():
    N, K = map(int, input().split())
    A = nCr(N - 1, 2) if N > 2 else 0
    if K > A:
        print(-1)
        return
    print(N - 1 + A - K)
    for i in range(2, N + 1):
        print(1, i)
    for u, v in islice(combinations(range(2, N + 1), 2), A - K):
        print(u, v)

main()

Buggy submission (verdict: Runtime Error):
from math import factorial
from itertools import combinations, islice

def nCr(n, r):
    return factorial(n) // factorial(r) // factorial(n - r)

def main():
    N, K = map(int, input().split())
    A = nCr(N - 1, 2)
    if K > A:
        print(-1)
        return
    print(N - 1 + A - K)
    for i in range(2, N + 1):
        print(1, i)
    for u, v in islice(combinations(list(range(2, N + 1)), 2), A - K):
        print(u, v)

main()

Buggy submission (verdict: Runtime Error):
from math import factorial
from itertools import combinations

def nCr(n, r):
    return factorial(n) // factorial(r) // factorial(n - r)

def main():
    N, K = map(int, input().split())
    A = nCr(N - 1, 2)
    if K > A:
        print(-1)
        return
    print(N - 1 + A - K)
    for i in range(2, N + 1):
        print(1, i)
    for u, v in list(combinations(list(range(2, N + 1)), 2))[:A - K]:
        print(u, v)

main()
Problem p03032 (python)

Fixed submission:
def main():
    N, K = map(int, input().split())
    V = list(map(int, input().split()))
    L = [(0, [])]
    R = [(0, [])]

    mp = 0
    mn = []
    for _, v in zip(range(K), V):
        if v >= 0:
            mp += v
        else:
            mn.append(v)
            mn.sort()
        L.append((mp, tuple(mn)))

    mp = 0
    mn = []
    for _, v in zip(range(K), reversed(V)):
        if v >= 0:
            mp += v
        else:
            mn.append(v)
            mn.sort()
        R.append((mp, tuple(mn)))

    mval = 0
    for l, (lp, ln) in enumerate(L):
        for r, (rp, rn) in zip(range(K - l + 1), R):
            if l + r > len(V):
                break
            val = rp + lp
            n = K - l - r
            if len(ln) + len(rn) > n:
                t = list(ln) + list(rn)
                t.sort()
                val += sum(t[n:])
            mval = max(mval, val)
    print(mval)


main()

Buggy submission (verdict: Runtime Error):
def main():
    N, K = map(int, input().split())
    V = list(map(int, input().split()))
    L = [(0, [])]
    R = [(0, [])]

    mp = 0
    mn = []
    for k in range(K):
        if k == len(V):
            break
        v = V[k]
        if v >= 0:
            mp += v
        else:
            mn.append(v)
            mn.sort()
        L.append((mp, tuple(mn)))

    mp = 0
    mn = []
    for k in range(K):
        i = len(V) - k - 1
        if i < 0:
            break
        v = V[i]
        if v >= 0:
            mp += v
        else:
            mn.append(v)
            mn.sort()
        R.append((mp, tuple(mn)))

    mval = 0
    for l in range(K + 1):
        if l == len(L) + 1:
            break
        lp, ln = L[l]
        for r in range(K - l):
            if l + r == len(V) or r == len(R) + 1:
                break
            rp, rn = R[r]
            val = rp + lp
            n = K - l - r
            if len(ln) + len(rn) > n:
                t = list(ln) + list(rn)
                t.sort()
                val += sum(t[n:])
            mval = max(mval, val)
    print(mval)


main()
Problem p03062 (python)

Fixed submission:
def main():
    N = int(input())
    A = list(map(int, input().split()))
    s = sum(abs(a) for a in A)
    if sum(1 for i in A if i < 0) & 1:
        s -= 2 * min(abs(a) for a in A)
    return s

print(main())

Buggy submission (verdict: Runtime Error):
def main():
    N = int(input())
    A = list(map(int, input().split()))
    Ap = sorted([i for i in A if i >= 0])
    An = sorted([i for i in A if i < 0])
    if len(An) % 2 == 0:
      return sum(Ap) - sum(An)
    return sum(Ap) - sum(An) - 2 * min(Ap[0], -An[-1])
print(main())
Problem p03128 (python)

Fixed submission:
def main():
    C = [2, 5, 5, 4, 5, 6, 3, 7, 6]
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    dp = [0] + [-1] * N
    K = {a: C[a - 1] for a in A}

    for i in range(min(K.values()), N + 1):
        try:
            dp[i] = max(dp[i - v] * 10 + k for k, v in K.items() if i - v >= 0 and dp[i - v] >= 0)
        except ValueError:
            dp[i] = -1
    print(dp[N])
main()

Buggy submission (verdict: Runtime Error):
def main():
    nums = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    As = {}
    for a in A:
        As[nums[a]] = max(a, As.get(nums[a], 0))
    A = sorted(list(As.values()), key=lambda x: nums[x])
    def helper(n, A):
        if n == 0:
            return []
        if n < 0:
            return None
        for i in A:
            s = helper(n - nums[i], A)
            if s is None:
                continue
            return s + [i]
        return None
            
    print(''.join(str(i) for i in sorted(helper(N, A), reverse=True)))

main()
Problem p03148 (python)

Fixed submission:
def main():
    N, K = map(int, input().split())
    TD = [tuple(map(int, input().split())) for _ in range(N)]
    TD.sort(key=lambda x: x[1], reverse=True)
    s = set()
    rep = []
    for t, d in TD[:K]:
        if t in s:
            rep.append(d)
        else:
            s.add(t)
    m = sum(d for _, d in TD[:K])
    p = len(s) ** 2 + m
    for t, d in TD[K:]:
        if not rep:
            break
        if t in s:
            continue
        m += d - rep.pop()
        s.add(t)
        p = max(p, len(s) ** 2 + m)
    return p

print(main())

Buggy submission (verdict: Runtime Error):
def main():
    N, K = map(int, input().split())
    TD = [tuple(map(int, input().split())) for _ in range(N)]
    TD.sort(key=lambda x: x[1], reverse=True)
    s = set()
    rep = []
    for t, d in TD[:K]:
        if t in s:
            rep.append(d)
        else:
            s.add(t)
    m = sum(d for _, d in TD[:K])
    p = len(s) ** 2 + m
    for t, d in TD[K:]:
        if t in s:
            continue
        m += d - rep.pop()
        s.add(t)
        p = max(p, len(s) ** 2 + m)
        if not rep:
            break
    return p

print(main())
Problem p03164 (python)

Fixed submission:
def printdp(dp):
    return
    print({i:v for i, v in enumerate(dp) if v < 10000})

def main():
    N, W = map(int, input().split())
    wv = [tuple(map(int, input().split())) for _ in range(N)]
    V = sum(v for _, v in wv)
    dp = [0] + [float('inf')] * V
    for wi, vi in wv:
        for i in range(V, vi - 1, -1):
            t = dp[i - vi] + wi
            if t < dp[i]:
                dp[i] = t
    for i in range(V, -1, -1):
        if dp[i] <= W:
            print(i)
            return


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
def main():
    N, W = map(int, input().split())
    wi, vi = map(int, input().split())
    dp = [0] * wi + [vi] * (W + 1 - wi)
    for _ in range(1, N):
        wi, vi = map(int, input().split())
        for i in range(W, wi - 1, -1):
            t = dp[i - wi] + vi
            if t > dp[i]:
                dp[i] = t
    print(dp[-1])


if __name__ == '__main__':
    main()
Problem p03169 (python)

Fixed submission:
from collections import Counter

def main():
    N = int(input())
    a = Counter(map(int, input().split()))
    a1, a2, a3 = a.get(1, 0), a.get(2, 0), a.get(3, 0)
    a123 = a1 + a2 + a3 + 1
    u = [[0.0] * (a123 - c2) for c2 in range(a123)]
    v = [[0.0] * (a123 - c2) for c2 in range(a123)]
    t1 = 0.0
    v2 = v[0]
    for c1 in range(1, a123):
        v2[c1] = t1 = N / c1 + t1
    for c2 in range(1, a123):
        v2 = v[c2]
        for c1, t2 in zip(range(301 - c2), v[c2 - 1][1:]):
            v2[c1] = t1 = (N + c1 * t1 + c2 * t2) / (c1 + c2)

    for c3 in range(1, a3 + 1):
        u, v = v, u
        v2 = v[0]
        for c1, t3 in zip(range(a123 - c3), u[1]):
            v2[c1] = t1 = (N + c1 * t1 + c3 * t3) / (c1 + c3)
        for c2 in range(1, a123 - c3):
            v2 = v[c2]
            c23 = c2 + c3
            for c1, t2, t3 in zip(range(a123 - c3 - c2), v[c2 - 1][1:], u[c2 + 1]):
                v2[c1] = t1 = (N + c1 * t1 + c2 * t2 + c3 * t3) / (c1 + c23)

    print(v[a2][a1])
main()

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

@lru_cache(maxsize=None)
def dp(N, c1, c2, c3):
    if c1 + c2 + c3 == 0:
        return 0
    r = N
    if c1:
        r += c1 * dp(N, c1 - 1, c2, c3)
    if c2:
        r += c2 * dp(N, c1 + 1, c2 - 1, c3)
    if c3:
        r += c3 * dp(N, c1, c2 + 1, c3 - 1)
    return r / (c1 + c2 + c3)

def main():
    N = int(input())
    a = list(map(int, input().split()))
    a = Counter(a)
    print(dp(N, a.get(1, 0), a.get(2, 0), a.get(3, 0)))


main()
Problem p03682 (python)

Fixed submission:
from operator import itemgetter
from scipy.sparse import lil_matrix, csr_matrix
from scipy.sparse.csgraph import minimum_spanning_tree

def main():
    N = int(input())
    M = 10**10
    XY = [tuple(map(int, input().split())) for _ in range(N)]
    xy = [(x, i) for i, (x, _) in enumerate(XY)]
    yx = [(y, i) for i, (_, y) in enumerate(XY)]
    xy.sort()
    yx.sort()
    d = {}
    x1, i1 = xy[0]
    for x, i in xy[1:]:
        t = (i1, i) if i1 < i else (i, i1)
        d[t] = min(abs(x1 - x), d.get(t, M))
        x1, i1 = x, i
    x1, i1 = yx[0]
    for x, i in yx[1:]:
        t = (i1, i) if i1 < i else (i, i1)
        d[t] = min(abs(x1 - x), d.get(t, M))
        x1, i1 = x, i
    row = list(map(itemgetter(0), d.keys()))
    col = list(map(itemgetter(1), d.keys()))
    c = csr_matrix((list(d.values()), (row, col)), shape=(N, N))
    a = minimum_spanning_tree(c, overwrite=True)
    return int(a.sum())

print(main())

Buggy submission (verdict: Runtime Error):
from operator import itemgetter
from scipy.sparse import lil_matrix, csr_matrix
from scipy.sparse.csgraph import minimum_spanning_tree

def main():
    N = int(input())
    M = 10**10
    XY = [tuple(map(int, input().split())) for _ in range(N)]
    xy = [(x, i) for i, (x, _) in enumerate(XY)]
    yx = [(y, i) for i, (_, y) in enumerate(XY)]
    xy.sort()
    yx.sort()
    d = {}
    x1, i1 = xy[0]
    for x, i in xy[1:]:
        t = (i1, i) if i1 < i else (i, i1)
        d[t] = min(abs(x1 - x), d.get(t, M))
        x1, i1 = x, i
    x1, i1 = yx[0]
    for x, i in yx[1:]:
        t = (i1, i) if i1 < i else (i, i1)
        d[t] = min(abs(x1 - x), d.get(t, M))
        x1, i1 = x, i
    row = list(map(itemgetter(0), d.keys()))
    col = list(map(itemgetter(1), d.keys()))
    c = csr_matrix((list(d.values()), (row, col)), shape=(N, N))
    a = minimum_spanning_tree(c, overwrite=True)
    return a.sum(dtype=int)

print(main())

Buggy submission (verdict: Runtime Error):
from scipy.sparse import lil_matrix
from scipy.sparse.csgraph import minimum_spanning_tree

def main():
    N = int(input())
    M = 10**10
    XY = [tuple(map(int, input().split())) for _ in range(N)]
    xy = [(x, i) for i, (x, _) in enumerate(XY)]
    yx = [(y, i) for i, (_, y) in enumerate(XY)]
    xy.sort()
    yx.sort()
    d = {}
    x1, i1 = xy[0]
    for x, i in xy[1:]:
        t = (i1, i) if i1 < i else (i, i1)
        d[t] = min(abs(x1 - x), d.get(t, M))
        x1, i1 = x, i
    x1, i1 = yx[0]
    for x, i in yx[1:]:
        t = (i1, i) if i1 < i else (i, i1)
        d[t] = min(abs(x1 - x), d.get(t, M))
        x1, i1 = x, i
    l = lil_matrix((N, N), dtype=int)
    for (i, j), t in d.items():
        l[i, j] = t
    a = minimum_spanning_tree(l.tocsr())
    return a.sum(dtype=int)

print(main())
Problem p03722 (python)

Fixed submission:
import sys
sys.setrecursionlimit(10**7)
def main():
    N, M = map(int, input().split())
    G = [[] for _ in range(N)]
    for _ in range(M):
        a, b, c = map(int, input().split())
        G[a - 1].append((b - 1, c))
    INF = 10 ** 40
    S = [-INF] * N
    S[0] = 0

    def helper(n, s, hist):
        for g, gc in G[n]:
            if S[g] >= s + gc or S[g] >= INF:
                continue
            S[g] = s + gc
            if g in hist:
                S[g] = INF
            hist[g] = hist.get(g, 0) + 1
            helper(g, S[g], hist)
            hist[g] -= 1
            if hist[g] == 0:
                del hist[g]
    helper(0, 0, {0: 1})
    s = S[-1]
    return s if s < INF else 'inf'

print(main())

Buggy submission (verdict: Runtime Error):
def main():
    N, M = map(int, input().split())
    G = [[] for _ in range(N)]
    for _ in range(M):
        a, b, c = map(int, input().split())
        G[a - 1].append((b - 1, c))
    INF = 10 ** 40
    S = [-INF] * N
    S[0] = 0

    cur = set([0])
    def helper(n, s, hist):
        for g, gc in G[n]:
            if S[g] > s + gc or S[g] >= INF:
                continue
            S[g] = s + gc
            if g in hist:
                S[g] = INF
            hist.add(g)
            helper(g, S[g], hist)
            if g in hist:
                hist.remove(g)
    helper(0, 0, set())
    s = S[-1]
    return s if s < INF else 'inf'

print(main())
Problem p03837 (python)

Fixed submission:
import heapq

def main():
    N, M = map(int, input().split())
    G = [[] for _ in range(N)]
    for _ in range(M):
        a, b, c = map(int, input().split())
        G[a - 1].append((b - 1, c))
        G[b - 1].append((a - 1, c))
    used = set()
    for i in range(N):
        H = []
        for b, c in G[i]:
            heapq.heappush(H, (c, i, b))
        D = [10**10] * N
        D[i] = 0
        while H:
            c, a, b = heapq.heappop(H)
            if D[b] < c:
                continue
            D[b] = c
            if a < b:
                used.add((a, b))
            else:
                used.add((b, a))
            for d, cc in G[b]:
                if D[d] > c + cc:
                    D[d] = c + cc
                    heapq.heappush(H, (c + cc, b, d))
    return M - len(used)

print(main())

Buggy submission (verdict: Runtime Error):
import heapq

def main():
    N, M = map(int, input().split())
    G = [[] for _ in range(N)]
    for _ in range(M):
        a, b, c = map(int, input().split())
        G[a - 1].append((b - 1, c))
        G[b - 1].append((a - 1, c))
    used = set()
    for i in range(N):
        H = []
        for b, c in G[i]:
            heapq.heappush(H, (c, i, b))
        todo = set(range(N))
        todo.remove(i)
        D = [10**10] * N
        D[i] = 0
        while H:
            c, a, b = heapq.heappop(H)
            if D[b] < c:
                continue
            D[b] = c
            if a < b:
                used.add((a, b))
            else:
                used.add((b, a))
            todo.remove(b)
            for d, cc in G[b]:
                if d in todo:
                    heapq.heappush(H, (c + cc, b, d))
    return M - len(used)

print(main())
Problem p02608 (python)

Fixed submission:

n = int(input())
ans_lis = [0 for _ in range(n)]
for x in range(1,101):
    for y in range(1, 101):
        for z in range(1, 101):
            f = x**2+y**2+z**2+x*y+y*z+z*x
            if f<=n:
                ans_lis[f-1]+=1
for ans in ans_lis:
    print(ans)

Buggy submission (verdict: Runtime Error):
ans_lis = [0 for _ in range(n)]
n = int(input())
for x in range(1,101):
    for y in range(1, 101):
        for z in range(1, 101):
            f = x**2+y**2+z**2+x*y+y*z+z*x
            if f<=n:
#                 print(f)
                ans_lis[f-1]+=1
for ans in ans_lis:
    print(ans)