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

Fixed submission:
# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline

#n,k,*a = map(int,read().split())

n, = map(int,readline().split())
vw = [[0,0]]+[list(map(int,readline().split())) for _ in range(n)]

def merge(av,aw,bv,bw):
    la,lb = len(aw),len(bw)
    rv = [0]*(la+lb)
    rw = [0]*(la+lb)
    ia = ib = 0
    for i in range(la+lb):
        if ib==lb or (ia < la and aw[ia] < bw[ib]):
            rv[i] = av[ia]
            rw[i] = aw[ia]
            ia += 1
        else:
            rv[i] = bv[ib]
            rw[i] = bw[ib]
            ib += 1
    return rv,rw

A = 10
N = min(1<<A,n+1)
memov = [[] for _ in range(N)]
memow = [[] for _ in range(N)]

memov[0] = [0]
memow[0] = [0]

#from itertools import acumulate
for i in range(1,N):
    v,w = vw[i]
    m2v = [v+v1 for v1 in memov[i>>1]]
    m2w = [w+w1 for w1 in memow[i>>1]]
    memov[i],memow[i] = merge(memov[i>>1],memow[i>>1],m2v,m2w)

    #memov[i] = list(accumulate(memov[i],max))
    for j in range(1,len(memov[i])):
        memov[i][j] = max(memov[i][j-1],memov[i][j])
    
def solve(lstv,lstw,dv,dw,l):
    ans = 0
    idx = len(lstw)-1
    #print(lstv,lstw,dv,dw,l)
    for v,w in zip(dv,dw):
        while idx >= 0 and lstw[idx] + w > l:
            idx -= 1
        if idx >= 0 and v+lstv[idx] > ans:
            ans = v+lstv[idx]
    print(ans)        
 
 

q, = map(int,readline().split())
for _ in range(q):
    u,l = map(int,readline().split())

    dv = [0]
    dw = [0]
    while u >= N:
        v,w = vw[u]
        m2v = [v+v1 for v1 in dv]
        m2w = [w+w1 for w1 in dw]
        dv,dw = merge(dv,dw,m2v,m2w)
        u >>= 1
    
    #for j in range(1,len(dv)):
    #    dv[j] = max(dv[j-1],dv[j])
    
    solve(memov[u],memow[u],dv,dw,l)

#print(memov)
#print(memow)

Buggy submission (verdict: Runtime Error):
# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline

#n,k,*a = map(int,read().split())

n, = map(int,readline().split())
vw = [[0,0]]+[list(map(int,readline().split())) for _ in range(n)]

#print(vw)
A = 9
N = min(1<<A,n+1)

memo = [None for _ in range(N)]
L = 10**5+1
memo[0] = [0]*L

from itertools import accumulate

for i in range(1,N):
    m = memo[i>>1][:]
    v,w = vw[i]    
    for j in range(L-1,w-1,-1):
        if m[j] < m[j-w]+v:
            m[j] = m[j-w]+v
    memo[i] = list(accumulate(m,max))


q, = map(int,readline().split())
for _ in range(q):
    u,l = map(int,readline().split())

    dic = [(0,0)]
    while u >= N:
        dic += [(vw[u][1]+w1,vw[u][0]+v1) for w1,v1 in dic]
        u >>= 1
    
    ans = 0    
    for w,v in dic:
        ans = max(ans,memo[u][l-v])
    print(ans)
Problem p02662 (python)

Fixed submission:
# coding: utf-8
# Your code here!
import sys
readline = sys.stdin.readline
read = sys.stdin.read

n,s,*a = map(int,read().split())

MOD = 998244353
def mul(c,m,dp): #multiply (2+x^c) up to x^m
    for i in range(m,c-1,-1):
        dp[i] *= 2
        dp[i] += dp[i-c]
        dp[i] %= MOD
    for i in range(min(m,c-1),-1,-1):
        dp[i] *= 2
        dp[i] %= MOD

    
dp = [0]*(s+1)
dp[0] = 1

for i in a:
    mul(i,s,dp)

print(dp[-1]%MOD)
#print(dp)

Buggy submission (verdict: Runtime Error):
# coding: utf-8
# Your code here!
import sys
readline = sys.stdin.readline
read = sys.stdin.read

n,s,*a = map(int,read().split())

MOD = 998244353
def mul(c,m,dp): #multiply (2+x^c) up to x^m
    for i in range(m,c-1,-1):
        dp[i] *= 2
        dp[i] += dp[i-c]
        dp[i] %= MOD
    for i in range(c-1,-1,-1):
        dp[i] *= 2
        dp[i] %= MOD

    
dp = [0]*(s+1)
dp[0] = 1

for i in a:
    mul(i,s,dp)

print(dp[-1]%MOD)
#print(dp)
Problem p02692 (python)

Fixed submission:
# coding: utf-8
# Your code here!
import sys
readline = sys.stdin.readline
read = sys.stdin.read

#n = int(input())
n,*a = [int(i) for i in readline().split()]
s = read().split()

ans = ""
ok = 1

d = {"AB":0,"BC":1,"AC":2}
d2 = "ABC"

if sum(a) >= 3 or sum(a) <= 1:
    for i in s:
        v = d[i]
        w = (v+1)%3
        if a[w] < a[v]: v,w = w,v
        a[v] += 1
        a[w] -= 1
        ans += d2[v]
        if a[w] < 0: ok = 0
    
        #print(i,a,d2[v])
    if ok:
        print("Yes")
        print(*ans,sep="\n")
    else:
        print("No")


#d = {"AB":0,"BC":1,"AC":2}
#d2 = "ABC"

else: # (1,1,0) or (2,0,0)型
    for idx,c in enumerate(s):
        v = d[c]
        w = (v+1)%3
        
        if a[v]==1 and a[w]==1 and idx<n-1 and s[idx+1] != c:#先読み
            vv = d[s[idx+1]]
            ww = (vv+1)%3
            r = [0]*3
            r[v] += 1; r[w] += 1; r[vv] += 1; r[ww] += 1
            vv = r.index(2)
            ww = (vv+1)%3 if vv==v else (vv-1)%3
            a[vv] += 1
            a[ww] -= 1
            ans += d2[vv]
            if a[ww] < 0: ok = 0
        else: 
            if a[w] < a[v]: v,w = w,v
            a[v] += 1
            a[w] -= 1
            ans += d2[v]
            if a[w] < 0: ok = 0
        
        #print(a,c,ans[-1])
        
    if ok:
        print("Yes")
        print(*ans,sep="\n")
    else:
        print("No")

Buggy submission (verdict: Runtime Error):
n,*a = map(int,input().split())
s = [[*input()] for _ in range(n)]
a = {p:q for p,q in zip("ABC",a)}
ans = ["Yes"]+[0]*n
def dfs(i):
	if i==n:
	    print("\n".join(ans))
	    exit()
	for p,m in [s[i],s[i][::-1]]:
		if a[p]:
		    a[p]+=1; a[m]-=1; ans[i+1]=p
		    dfs(i+1)
		    a[p]-=1; a[m]+=1
dfs(0)
print("No")
Problem p02787 (python)

Fixed submission:
# coding: utf-8
# Your code here!
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
read = sys.stdin.read

#n,*w = [int(i) for i in read().split()]
#n,*t = map(int,read().split())

#n = int(input())
#s = input()
h,n = [int(i) for i in readline().split()]

 
def div(m,a,b,dp): #divide by (1+bx^a) up to x^m
    for i in range(m-a+1):
        dp[i+a] = min(dp[i+a], dp[i]+b)
    for i in range(max(m-a+1,0),m):
        dp[-1] = min(dp[-1],dp[i]+b)
        #dp[i+c] += dp[i]


INF = 10**9+7
dp =[INF]*(h+1)
dp[0] = 0

for _ in range(n):
    a,b = [int(i) for i in readline().split()]
    div(h,a,b,dp)
    #print(a,b,dp)
 


print(dp[-1])

Buggy submission (verdict: Runtime Error):
# coding: utf-8
# Your code here!
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
read = sys.stdin.read

#n,*w = [int(i) for i in read().split()]
#n,*t = map(int,read().split())

#n = int(input())
#s = input()
h,n = [int(i) for i in readline().split()]

 
def div(m,a,b,dp): #divide by (1+bx^a) up to x^m
    for i in range(m-a+1):
        dp[i+a] = min(dp[i+a], dp[i]+b)
    for i in range(m-a+1,m):
        dp[-1] = min(dp[-1],dp[i]+b)
        #dp[i+c] += dp[i]


INF = 10**9+7
dp =[INF]*(h+1)
dp[0] = 0

for _ in range(n):
    a,b = [int(i) for i in readline().split()]
    div(h,a,b,dp)
    #print(a,b,dp)
 


print(dp[-1])
Problem p02813 (python)

Fixed submission:
# coding: utf-8
# Your code here!
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
read = sys.stdin.read

n = int(input())
p = tuple([int(i) for i in readline().split()])
q = tuple([int(i) for i in readline().split()])

if p == q:
    print(0)
    exit()

from itertools import permutations
L = list(range(1,n+1))
for i,c in enumerate(permutations(L)):
    if c == p:
        a = i
    elif c == q:
        b = i

print(abs(a-b))

Buggy submission (verdict: Runtime Error):
# coding: utf-8
# Your code here!
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
read = sys.stdin.read

n = int(input())
p = tuple([int(i) for i in readline().split()])
q = tuple([int(i) for i in readline().split()])


from itertools import permutations
L = list(range(1,n+1))
for i,c in enumerate(permutations(L)):
    if c == p:
        a = i
    elif c == q:
        b = i

print(abs(a-b))
Problem p02840 (python)

Fixed submission:

# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline 
readlines = sys.stdin.readlines

#n = int(input())
from fractions import gcd

n,x,d = [int(i) for i in readline().split()]

g = gcd(x,d) 

if d < 0:
    x = x+(n-1)*d
    d = -d

if d == 0:
    if x == 0: print(1)
    else: print(n+1)
    exit()

kind = abs(d//g) #あまりは kind = d//g 種類 

ans = 0



for i in range(min(kind,n+2)):
    res = []
    for j in range(i,n+1,kind):
        res.append([j*x+j*(j-1)//2*d, j*x+(j*n-j*(j+1)//2)*d])
    
    if not res: continue
    
    #print(res)
    res.sort()
    
    q = [res[0][:]]

    for e,f in res:
        while q:
            a,b = q[-1]
            if b < e: break
            else:
                q.pop()
                e,f = a,max(b,f)
        
        q.append([e,f])
    
    #print(q)
    for a,b in q:
        ans += (b-a)//d + 1


print(ans)

Buggy submission (verdict: Runtime Error):

# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline 
readlines = sys.stdin.readlines

#n = int(input())
from math import gcd

n,x,d = [int(i) for i in readline().split()]

g = gcd(x,d) 

if d < 0:
    x = x+(n-1)*d
    d = -d

if d == 0:
    if x == 0: print(1)
    else: print(n+1)
    exit()

kind = d//g #あまりは kind = d//g 種類 

ans = 0


for i in range(kind):
    res = []
    for j in range(i,n+1,kind):
        res.append([j*x+j*(j-1)//2*d, j*x+(j*n-j*(j+1)//2)*d])
    
    if not res: continue
    
    #print(res)
    res.sort()
    
    q = [res[0][:]]

    for e,f in res:
        while q:
            a,b = q[-1]
            if b < e: break
            else:
                q.pop()
                e,f = a,max(b,f)
        
        q.append([e,f])
    
    #print(q)
    for a,b in q:
        ans += (b-a)//d + 1


print(ans)
Problem p02867 (python)

Fixed submission:
# coding: utf-8
# Your code here!

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline 

n = int(input())
a = [int(i) for i in readline().split()]
b = [int(i) for i in readline().split()]
pb = [(bi,i) for i,bi in enumerate(b)]

sa = sorted(a)
sb = sorted(b)
pb.sort()

na = [a[i] for bi,i in pb]


ok = 1
for i,j in zip(sa,sb):
    if i > j: ok = 0

for i,j in zip(sa[1:],sb):
    if i <= j: break
else:
    #sa => na が巡回置換か？
    d = {ai:i for i,ai in enumerate(sa)}
    ra = [d[ai] for ai in na]
    
    #print(ra,ok)    
    now = 0
    for i in range(n-1):
        now = ra[now]
        #print(now)
        if now == 0:
            break
    else: ok = 0    


    

#print(a,b,sa,sb,na)

if ok: print("Yes")    
else: print("No")

Buggy submission (verdict: Runtime Error):
# coding: utf-8
# Your code here!

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline 

n = int(input())
a = [int(i) for i in readline().split()]
b = [int(i) for i in readline().split()]
pb = [(bi,i) for i,bi in enumerate(b)]

sa = sorted(a)
sb = sorted(b)
pb.sort()

#na = [a[i] for bi,i in pb]
na = []
from itertools import groupby
for k,g in groupby(pb,key=lambda x: x[0]):
    g = list(g)
    res = [a[i] for bi,i in g]
    res.sort()
    #print(g,res)
    na += res

ok = 1
for i,j in zip(sa,sb):
    if i > j: ok = 0

for i,j in zip(sa[1:],sb):
    if i <= j: break
else:
    if na == sa[1:] + sa[:1]:
        ok = 0
    else: a(1)
    
#print(a,b,sa,sb,na)

if ok: print("Yes")    
else: print("No")
Problem p02886 (python)

Fixed submission:
# coding: utf-8
# Your code here!


import sys
#sys.setrecursionlimit(10**6)
readline = sys.stdin.readline 

n = int(input())
d = [int(i) for i in readline().split()]

ans = 0
for i in range(n):
    for j in range(i+1,n):
        ans += d[i]*d[j]
        

print(ans)

Buggy submission (verdict: Runtime Error):
3
3 1 2
Problem p02936 (python)

Fixed submission:
# coding: utf-8
# Your code here!

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline #文字列入力のときは注意

#n = int(input())
n,q = [int(i) for i in readline().split()]

g = [[] for _ in range(n)]
for i in range(n-1):
    a,b = [int(i) for i in readline().split()]
    g[a-1].append(b-1)
    g[b-1].append(a-1)

add = [0]*n
for _ in range(q):
    p,x = [int(i) for i in readline().split()]
    add[p-1] += x

ans = [0]*n
#ans[0] = add[0]

def dfs(v,p,value): #p: parent of v
    value += add[v]
    ans[v] = value
    for c in g[v]:
        if c == p: continue
        dfs(c,v,value)

dfs(0,-1,0)

#print(add)

print(*ans)

Buggy submission (verdict: Runtime Error):
# coding: utf-8
# Your code here!

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline #文字列入力のときは注意

#n = int(input())
def main():
    n,q = [int(i) for i in readline().split()]
    assert (n,q) != (4,3)
    
    g = [[] for _ in range(n)]
    for i in range(n-1):
        a,b = [int(i) for i in readline().split()]
        g[a-1].append(b-1)
        g[b-1].append(a-1)

    add = [0]*n
    for _ in range(q):
        p,x = [int(i) for i in readline().split()]
        add[p-1] += x

    ans = [0]*n
    #ans[0] = add[0]

    def dfs(v,p,value): #p: parent of v
        value += add[v]
        ans[v] = value
        for c in g[v]:
            if c == p: continue
            dfs(c,v,value)

    dfs(0,-1,0)

#print(add)

    print(*ans)


main()
Problem p02974 (python)

Fixed submission:
# coding: utf-8
# Your code here!
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline #文字列入力のときは注意

n,m = [int(i) for i in readline().split()]
MOD = 10**9+7

#dp[i][j][k]
# iまで見て j個未確定、k点
dp = [[[0 for k in range(n*n+1)] for j in range(n+1)] for i in range(n+1)]

dp[0][0][0] = 1

for i in range(n):
    for j in range(i+1):
        for k in range(n*n):
            if k + 2*j >= n*n: continue
            dp[i+1][j+1][k+2*j] += dp[i][j][k]
            dp[i+1][j+1][k+2*j] %= MOD
            dp[i+1][j  ][k+2*j] += (2*j+1)*dp[i][j][k]
            dp[i+1][j  ][k+2*j] %= MOD
            dp[i+1][j-1][k+2*j] += j*j*dp[i][j][k]
            dp[i+1][j-1][k+2*j] %= MOD
    

ans = dp[-1][0][m]
print(ans)

Buggy submission (verdict: Runtime Error):
# coding: utf-8
# Your code here!
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline #文字列入力のときは注意

n,m = [int(i) for i in readline().split()]
MOD = 10**9+7

#dp[i][j][k]
# iまで見て j個未確定、k点
dp = [[[0 for k in range(n*n)] for j in range(n+1)] for i in range(n+1)]

dp[0][0][0] = 1

for i in range(n):
    for j in range(i+1):
        for k in range(n*n):
            if k + 2*j >= n*n: continue
            dp[i+1][j+1][k+2*j] += dp[i][j][k]
            dp[i+1][j+1][k+2*j] %= MOD
            dp[i+1][j  ][k+2*j] += (2*j+1)*dp[i][j][k]
            dp[i+1][j  ][k+2*j] %= MOD
            dp[i+1][j-1][k+2*j] += j*j*dp[i][j][k]
            dp[i+1][j-1][k+2*j] %= MOD
    

#print(*dp,sep="\n")

ans = dp[-1][0][m]
print(ans)
Problem p03063 (python)

Fixed submission:
# coding: utf-8
# Your code here!
import sys, collections, bisect, math, itertools
from fractions import gcd 
#input = sys.stdin.readline #文字列入力のときは注意

n = int(input())
s = input()
#a = [int(i) for i in input().split()]
#m = [[int(i) for i in input().split()] for j in range(n)] # 縦「n」行

b = [0]*(n+1)
for i in range(n):
    b[i+1] += b[i] + (1 if s[i]=="#" else 0)

w = [0]*(n+1)
for i in range(n):
    w[i+1] += w[i] + (1 if s[i]=="." else 0)
#print(b,w)
ans = n
for i in range(n):
    if i != 0:
        p = b[i-1]
    else: p=0
    q = w[n]-w[i]
#    print(p,q)
    ans = min(ans,p+q)

print(min(ans,b[n]))

Buggy submission (verdict: Runtime Error):
# coding: utf-8
# Your code here!
import sys, collections, bisect, math, itertools
from fractions import gcd 
#input = sys.stdin.readline #文字列入力のときは注意

m = int(input())
#s = input()
#a = [int(i) for i in input().split()]
a = [int(input()) for j in range(m+1)] # 縦「n」行

beki = 0
while a[-1] == 0:
    a.pop()
    beki+=1
if m != len(a)-1:
    m = len(a)
    a.append(0)


def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]
allprimes = get_sieve_of_eratosthenes(10010)

primes=[]
def get_sieve_of_eratosthenes2():
    prime = []
    data = [i + 1 for i in range(1, 35000)]
    c=abs(a[m])
    while True:
        p = data[0]
        if 35000 <= p*p:
            return prime + data
        if c%p==0: primes.append(p)
        prime.append(p)
        data = [e for e in data if e % p != 0]

primes2=[]
def get_sieve_of_eratosthenes3():
    prime = []
    data = [i + 1 for i in range(1, 35000)]
    c=abs(a[0])
    while True:
        p = data[0]
        if 35000 <= p*p:
            return prime + data
        if c%p==0: primes2.append(p)
        prime.append(p)
        data = [e for e in data if e % p != 0]


get_sieve_of_eratosthenes2()
#print(primes)
if len(primes) == 0 and abs(a[m]) != 1:
    primes.append(abs(a[m]))
if len(primes2) == 0 and abs(a[0]) != 1:
    primes2.append(abs(a[0]))
n=m
if a[m]==0:
    primes = allprimes


primes = primes + primes2
#print(a)
#print(primes)
for p in primes:
    if p > 10**4+5:
        if sum([i%p for i in a]) == 0:
            print(p)
        continue
    coeff = list(reversed(a))
    while len(coeff) > p:
#        print(coeff,p)
        t=coeff.pop()
        coeff[-p+1]+=t
            
#    print(coeff)
    if sum([i%p for i in coeff]) == 0:
        print(p)
Problem p03083 (python)

Fixed submission:
#a,b,c = [int(i) for i in input().split()]

import sys
input = sys.stdin.readline

SIZE=200002; 
MOD = 10**9+7
bai= 500000000+4

inv = [0]*(SIZE+1)# inv[j] = j^{-1} mod MOD
fac = [0]*(SIZE+1)# fac[j] = j! mod MOD
finv = [0]*(SIZE+1)# finv[j] = (j!)^{-1} mod MOD
inv[1] = 1
fac[0] = fac[1] = 1
finv[0] = finv[1] = 1
for i in range(2,SIZE+1):
    inv[i] = MOD -(MOD//i)*inv[MOD%i]%MOD
    fac[i] = fac[i-1]*i%MOD
    finv[i]= finv[i-1]*inv[i]%MOD

def choose(n,r): # nCk mod MOD の計算
    if 0 <= r <= n:
        return (fac[n]*finv[r]%MOD)*finv[n-r]%MOD
    else:
        return 0



b,w = [int(i) for i in input().split()]

c = min(b,w)
for i in [0]*c:
    print(bai)

ans = bai
p=pow(bai,c+1,MOD)
for i in range(c,b+w):
#    print(p,i-1,i-w,b-1)
    ans += p*(choose(i-1,i-w) - choose(i-1,b-1))
    p= p*bai; p%=MOD
    ans = ans%MOD
    print(ans)

Buggy submission (verdict: Runtime Error):
#a,b,c = [int(i) for i in input().split()]

import sys
input = sys.stdin.readline

SIZE=200002; 
MOD = 10**9+7
2bai= 500000000+4

inv = [0]*(SIZE+1)# inv[j] = j^{-1} mod MOD
fac = [0]*(SIZE+1)# fac[j] = j! mod MOD
finv = [0]*(SIZE+1)# finv[j] = (j!)^{-1} mod MOD
inv[1] = 1
fac[0] = fac[1] = 1
finv[0] = finv[1] = 1
for i in range(2,SIZE+1):
    inv[i] = MOD -(MOD//i)*inv[MOD%i]%MOD
    fac[i] = fac[i-1]*i%MOD
    finv[i]= finv[i-1]*inv[i]%MOD

def choose(n,r): # nCk mod MOD の計算
    if 0 <= r <= n:
        return (fac[n]*finv[r]%MOD)*finv[n-r]%MOD
    else:
        return 0



b,w = [int(i) for i in input().split()]

ans = [0]*(b+1)
ans[x] = 1

c = min(b,w)
for i in [0]*c:
    print(2bai)

ans = 2bai
for i in range(c,b+w+1):
    ans += pow(2,i-1,MOD)*(choose(i-1,i-1-w) - choose(i-1,b-1)
    ans %= MOD
    print(ans)
Problem p03106 (python)

Fixed submission:

a,b,k=[int(i) for i in input().split()]


c=0

ans = 1
for i in range(1000,1,-1):
    if a%i ==0 and b%i==0:
        c+=1
    if c == k:
        ans = i
        break

print(ans)

Buggy submission (verdict: Runtime Error):

a,b,k=[int(i) for i in input().split()]


c=0

for i in range(1000,1,-1):
    if a%i ==0 and b%i==0:
        c+=1
    if c == k:
        ans = i
        break

print(ans)
Problem p03166 (python)

Fixed submission:
# coding: utf-8
# Your code here!
import sys
sys.setrecursionlimit(10**6)

n,m = [int(i) for i in input().split()]

#ko = [[] for _ in range(n)]
oya = [[] for _ in range(n)]
for _ in range(m):
    x,y = [int(i)-1 for i in input().split()]
#    ko[x].append(y)
    oya[y].append(x)

memo = [-1]*n

def longest(v): #nを終点とするlongest
    if memo[v] >= 0:
        return memo[v]
    else:
        c=0
        for j in oya[v]:
            c = max(c,longest(j)+1)
        memo[v] = c
        return c

for i in range(n):
    longest(i)

print(max(memo))    
#print(memo)

Buggy submission (verdict: Runtime Error):
# coding: utf-8
# Your code here!
from functools import lru_cache


n,m = [int(i) for i in input().split()]

#ko = [[] for _ in range(n)]
oya = [[] for _ in range(n)]
for _ in range(m):
    x,y = [int(i)-1 for i in input().split()]
#    ko[x].append(y)
    oya[y].append(x)

#memo = [-1]*n

@lru_cache(maxsize=None)
def longest(v): #nを終点とするlongest
#    if memo[v] >= 0:
#        return memo[v]
#    else:
    if oya[v]:
        return max([longest(j)+1 for j in oya[v]])
    else:
        return 0
        
    

memo = [longest(i) for i in range(n)]

print(max(memo))    
#print(memo)

Buggy submission (verdict: Runtime Error):
# coding: utf-8
# Your code here!
from functools import lru_cache


n,m = [int(i) for i in input().split()]

#ko = [[] for _ in range(n)]
oya = [[] for _ in range(n)]
for _ in range(m):
    x,y = [int(i)-1 for i in input().split()]
#    ko[x].append(y)
    oya[y].append(x)

#memo = [-1]*n

@lru_cache()
def longest(v): #nを終点とするlongest
#    if memo[v] >= 0:
#        return memo[v]
#    else:
    c=0
    for j in oya[v]:
        c = max(c,longest(j)+1)
#    memo[v] = c
    return c

memo = [longest(i) for i in range(n)]

print(max(memo))    
#print(memo)

Buggy submission (verdict: Runtime Error):
# coding: utf-8
# Your code here!

n,m = [int(i) for i in input().split()]

#ko = [[] for _ in range(n)]
oya = [[] for _ in range(n)]
for _ in range(m):
    x,y = [int(i)-1 for i in input().split()]
#    ko[x].append(y)
    oya[y].append(x)

memo = [-1]*n

def longest(v): #nを終点とするlongest
    if memo[v] >= 0:
        return memo[v]
    else:
        c=0
        for j in oya[v]:
            c = max(c,longest(j)+1)
        memo[v] = c
        return c

for i in range(n):
    longest(i)

print(max(memo))    
#print(memo)
Problem p03170 (python)

Fixed submission:
# coding: utf-8
# Your code here!
import sys
sys.setrecursionlimit(10**7)

n,k = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
a.sort()

# 1:先手　-1:後手
memo = [0]*(k+1)
def dp(x):
    if memo[x] != 0:
        return memo[x]
    for i in a:
        if x < i: break
        else:
            if dp(x-i) == -1:
                memo[x] = 1
                return 1
    memo[x] = -1
    return -1

if dp(k)==1:
    print("First")
else:
    print("Second")

Buggy submission (verdict: Runtime Error):
# coding: utf-8
# Your code here!
from functools import lru_cache

n,k = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
a.sort()

# 1:先手　-1:後手
@lru_cache(maxsize=None)
def dp(x):
    for i in a:
        if x < i:
            return -1
        else:
            if dp(x-i) == -1:
                return 1
    return -1


if dp(k)==1:
    print("First")
else:
    print("Second")
Problem p03175 (python)

Fixed submission:
# coding: utf-8
# Your code here!
import sys
sys.setrecursionlimit(10**7)
MOD=10**9+7

n=int(input())
edge=[[] for _ in range(n)]
for _ in range(n-1):
    p,q = [int(i)-1 for i in input().split()]
    edge[p].append(q)
    edge[q].append(p)

    
used = [0]*n
ansb = [0]*n
answ = [0]*n

def dfs(x):
    if used[x]: return (ansb[x], answ[x])
    used[x] = 1
    cb=1; cw=1;
    for e in edge[x]:
        if used[e]: continue
        eb,ew = dfs(e)
        cb*=ew
        cb%=MOD
        cw*=(eb+ew)
        cw%=MOD        
    ansb[x]=cb
    answ[x]=cw
    return (cb,cw)

print(sum(dfs(0))%MOD)

#print(used)
#print(ansb)
#print(answ)

Buggy submission (verdict: Runtime Error):
# coding: utf-8
# Your code here!
n=int(input())
edge=[[] for _ in range(n)]
for _ in range(n-1):
    p,q = [int(i)-1 for i in input().split()]
    edge[p].append(q)
    edge[q].append(p)

    
used = [0]*n
ansb = [0]*n
answ = [0]*n

def dfs(x):
    if used[x]: return (ansb[x], answ[x])
    used[x] = 1
    cb=1; cw=1;
    for e in edge[x]:
        if used[e]: continue
        eb,ew = dfs(e)
        cb*=ew
        cw*=(eb+ew)
    ansb[x]=cb
    answ[x]=cw
    return (cb,cw)

print(sum(dfs(0)))

#print(used)
#print(ansb)
#print(answ)