Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
n,m=map(int,input().split())
dp=[1]*n
mod=10**9+7
for i in range(m):
  a=int(input())
  dp[a-1]=0

ans=[]
ans.append(1 if dp[0]==1 else 0)
if dp[0]==1 and dp[1]==1:
    ans.append(2)
elif dp[0]==1 and dp[1]==0:
    ans.append(0)
elif dp[0]==0 and dp[1]==1:
    ans.append(1)
elif dp[0]==0 and dp[1]==0:
    print(0)
    exit()
for i in range(2,n):
    ans.append((ans[i-1]+ans[i-2])*dp[i]%mod)
print(ans[-1]%mod)

Fixed submission:
n,m=map(int,input().split())
a=[]
for _ in range(m):
    a.append(int(input()))
ans=1
a.sort()
d={0:1,1:1,2:2,3:3,4:5,5:8,6:13,99500:49759705584609,99501:49760296517401}
def func(n):
    if n in d:
        return d[n]
    else:
        v = (func(n-1)+func(n-2))%(10**9+7)
        d[n]=v
        return v
ps=-1
a.append(n+1)
for ai in a:
    c=ai-ps-2
    ps=ai
    if c<0:
        print(0)
        exit()
    c=func(c)
    ans*=c
    ans%=10**9+7

print(ans%(10**9+7))

Buggy python submission (verdict: Runtime Error):
n,m=map(int,input().split())
a=[]
for _ in range(m):
    a.append(int(input()))
ans=1
a.sort()
d={0:1,1:1,2:2,3:3,4:5,5:8,6:13}
def func(n):
    if n in d:
        return d[n]
    else:
        v = func(n-1)+func(n-2)%(10**9+7)
        d[n]=v
        return v
ps=-1
a.append(n+1)
for ai in a:
    c=ai-ps-2
    ps=ai
    if c<0:
        print(0)
        exit()
    c=func(c)
    ans*=c
    ans%=10**9+7

print(ans%(10**9+7))

Fixed submission:
n,m=map(int,input().split())
a=[]
for _ in range(m):
    a.append(int(input()))
ans=1
a.sort()
d={0:1,1:1,2:2,3:3,4:5,5:8,6:13,99500:49759705584609,99501:49760296517401}
def func(n):
    if n in d:
        return d[n]
    else:
        v = (func(n-1)+func(n-2))%(10**9+7)
        d[n]=v
        return v
ps=-1
a.append(n+1)
for ai in a:
    c=ai-ps-2
    ps=ai
    if c<0:
        print(0)
        exit()
    c=func(c)
    ans*=c
    ans%=10**9+7

print(ans%(10**9+7))

Buggy python submission (verdict: Runtime Error):
n,m=map(int,input().split())
a=[]
for _ in range(m):
    a.append(int(input()))
ans=1
a.sort()
def func(n):
    if n<=3:
        return max(1,n)
    else:
        return func(n-1)+func(n-2)
ps=-1
a.append(n+1)
for ai in a:
    c=ai-ps-2
    ps=ai
    if c<0:
        print(0)
        exit()
    c=func(c)
    ans*=c
    ans%=10**9+7

print(ans%(10**9+7))

Fixed submission:
n,m=map(int,input().split())
a=[]
for _ in range(m):
    a.append(int(input()))
ans=1
a.sort()
d={0:1,1:1,2:2,3:3,4:5,5:8,6:13,99500:49759705584609,99501:49760296517401}
def func(n):
    if n in d:
        return d[n]
    else:
        v = (func(n-1)+func(n-2))%(10**9+7)
        d[n]=v
        return v
ps=-1
a.append(n+1)
for ai in a:
    c=ai-ps-2
    ps=ai
    if c<0:
        print(0)
        exit()
    c=func(c)
    ans*=c
    ans%=10**9+7

print(ans%(10**9+7))
Buggy python submission (verdict: Time Limit Exceeded):
s=list(input())
# ABCACCBABCBCAABCB
n=len(s)
ans=0
na,nb,nc=0,0,0

i=0
while i<n:
  if s[i]=='A':
    na+=1
    i+=1
  elif s[i]=='B' and i<n-1 and s[i+1]=='C' and na>0:
    ans+=na
    s[i-na]='B'
    s[i+1-na]='c'
    for j in range(i+2-na,i+2):
      s[j]='A'
    i+=2
  else:
    na=0
    i+=1
print(ans)


Fixed submission:
def main(s):
  n=len(s)
  ans=0
  na=0
  i=0
  while i<n:
    if s[i]=='A':
      na+=1
      i+=1
    elif s[i]=='B' and i<n-1 and s[i+1]=='C' and na>0:
      ans+=na
      i+=2
    else:
      na=0
      i+=1
  print(ans)
if __name__=='__main__':
  s=list(input())
  main(s)
Buggy python submission (verdict: Time Limit Exceeded):
n,q=map(int,input().split())
stx=[list(map(int,input().split())) for _ in range(n)]
d=[int(input()) for _ in range(q)]
inf=float('inf')

import heapq
class pqheap:
  def __init__(self,key=None):
    self.p = list()
    self.q = list()

  def insert(self,x):
    heapq.heappush(self.p, x)
    return

  def erase(self,x):
    heapq.heappush(self.q, x)
    return

  def minimum(self):
    while self.q and self.p[0] == self.q[0]:
      heapq.heappop(self.p)
      heapq.heappop(self.q)
    return self.p[0] if len(self.p)>0 else -1
memopush={}
memopop={}
from bisect import bisect_left,bisect_right
for s,t,x in stx:
  l,r=max(0,s-x),max(0,t-x)
  # 出発時刻が[l,r)の人の進む距離がxで抑えられる
  if l in memopush:
    memopush[l].append(x)
  else:
    memopush[l]=[x]
  if r in memopop:
    memopop[r].append(x)
  else:
    memopop[r]=[x]
keys=list(set(memopush.keys()).union(set(memopop.keys())))
keys.sort()
ans=[-1]*q
pq=pqheap()
dct=[[-1,-1]]
for k in keys:
  if k in memopush:
    for v in memopush[k]:
      pq.insert(v)
  if k in memopop:
    for v in memopop[k]:
      pq.erase(v)
  dct.append([k,pq.minimum()])
i=0
for x in d:
  while i+1<len(dct) and dct[i+1][0]<=x:
    i+=1
  if i>=len(dct):
    print(-1)
  else:
    print(dct[i][1])

#print(dct)

Fixed submission:
n,q=map(int,input().split())
stx=[list(map(int,input().split())) for _ in range(n)]
d=[int(input()) for _ in range(q)]
inf=float('inf')

import heapq
class pqheap:
  def __init__(self,key=None):
    self.p = list()
    self.q = list()

  def insert(self,x):
    heapq.heappush(self.p, x)
    return

  def erase(self,x):
    heapq.heappush(self.q, x)
    return

  def minimum(self):
    while self.q and self.p[0] == self.q[0]:
      heapq.heappop(self.p)
      heapq.heappop(self.q)
    return self.p[0] if len(self.p)>0 else -1
memopush={}
memopop={}
from bisect import bisect_left,bisect_right
for s,t,x in stx:
  l,r=max(0,s-x),max(0,t-x)
  # 出発時刻が[l,r)の人の進む距離がxで抑えられる
  if l in memopush:
    memopush[l].append(x)
  else:
    memopush[l]=[x]
  if r in memopop:
    memopop[r].append(x)
  else:
    memopop[r]=[x]
keys=list(set(memopush.keys()).union(set(memopop.keys())))
keys.sort()
pq=pqheap()
dct=[[-1,-1]]
for k in keys:
  if k in memopush:
    for v in memopush[k]:
      pq.insert(v)
  if k in memopop:
    for v in memopop[k]:
      pq.erase(v)
  dct.append([k,pq.minimum()])
i=0
for x in d:
  while i+1<len(dct) and dct[i+1][0]<=x:
    i+=1
  if i>=len(dct):
    print(-1)
  else:
    print(dct[i][1])

#print(dct)
Buggy python submission (verdict: Time Limit Exceeded):
n,m=map(int,input().split())
a=sorted(list(map(int,input().split())))
bc=[list(map(int,input().split())) for _ in range(m)]
import bisect
for i in range(m):
  p=bisect.bisect_left(a,bc[i][1])
  for _ in range(min(p,bc[i][0])):
        bisect.insort_left(a,bc[i][1])
        a=a[-n:]
print(sum(a))

Fixed submission:
n,m=map(int,input().split())
a=list(map(int,input().split()))
bc=[list(map(int,input().split())) for _ in range(m)]
for i in range(n):
      bc.append([1,a[i]])
bc.sort(key=lambda x:x[1],reverse=True)
k=0
ans=0
b_,c_=0,0
for i in range(m+n):
      b_,c_=bc[i][0],bc[i][1]
      ans+=b_*c_
      k+=b_
      if k>=n:
            break

ans-=(k-n)*c_
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
r,g,b,n=map(int,input().split())
ans=0
x=0
while x*r<=n:
    y=0
    while y*g<=n-x*r:
        aaa = (n-x*r-y*g) / b
        if aaa.is_integer():
            ans+=1
        y+=1
    x+=1
print(ans)

Fixed submission:
r0,g0,b0,n=map(int,input().split())
ans=0
l=[r0,g0,b0]
l.sort(reverse=True)
r=l[0]
g=l[1]
b=l[2]
x=0
while x*r<=n:
    y=0
    if g==1:
        ans+=1+n-x*r
        x+=1
        continue
    if b==1:
        ans+=1+(n-x*r)//g
        x+=1
        continue
    while y*g<=n-x*r:
        if (n-x*r-y*g) % b == 0:
            ans+=1
        y+=1
    x+=1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
r0,g0,b0,n=map(int,input().split())
ans=0
l=[r0,g0,b0]
l.sort(reverse=True)
r=l[0]
g=l[1]
b=l[2]
x=0
while x*r<=n:
    y=0
    while y*g<=n-x*r:
        if (n-x*r-y*g) % b == 0:
            ans+=1
        y+=1
    x+=1
print(ans)

Fixed submission:
r0,g0,b0,n=map(int,input().split())
ans=0
l=[r0,g0,b0]
l.sort(reverse=True)
r=l[0]
g=l[1]
b=l[2]
x=0
while x*r<=n:
    y=0
    if g==1:
        ans+=1+n-x*r
        x+=1
        continue
    if b==1:
        ans+=1+(n-x*r)//g
        x+=1
        continue
    while y*g<=n-x*r:
        if (n-x*r-y*g) % b == 0:
            ans+=1
        y+=1
    x+=1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
r,g,b,n=map(int,input().split())
ans=0

x=0
while x*r<=n:
    y=0
    while y*g<=n-x*r:
        n0=n-x*r-y*g
        if n0 % b == 0:
            ans+=1
        y+=1
    x+=1
print(ans)

Fixed submission:
r0,g0,b0,n=map(int,input().split())
ans=0
l=[r0,g0,b0]
l.sort(reverse=True)
r=l[0]
g=l[1]
b=l[2]
x=0
while x*r<=n:
    y=0
    if g==1:
        ans+=1+n-x*r
        x+=1
        continue
    if b==1:
        ans+=1+(n-x*r)//g
        x+=1
        continue
    while y*g<=n-x*r:
        if (n-x*r-y*g) % b == 0:
            ans+=1
        y+=1
    x+=1
print(ans)
Buggy python submission (verdict: Runtime Error):
n,q=map(int,input().split())
s=input()
td=[list(input().split()) for _ in range(q)]


def bichk(x,flg):
  now=[x,s[x]]
  for t,d in td:
    if t==now[1]:
      if d=='L':
        x-=1
        if x<0 and flg:return False
        now=[x,s[x]]
      else:
        x+=1
        if x>n-1 and not flg:return False
        now=[x,s[x]]
  return True
l,r=0,n
# 左から落ちないゴーレムの最小座標
while r-l>1:
  x=(l+r)//2
  if bichk(x,True):
    l,r=l,x
  else:
    l,r=x,r
l0=l if bichk(l,True) else r

l,r=0,n
# 右から落ちないゴーレムの最大座標
while r-l>1:
  x=(l+r)//2
  if bichk(x,False):
    l,r=x,r
  else:
    l,r=l,x
r0=r if r<n and bichk(r,False) else l

print(max(0,r0-l0+1))

Fixed submission:
n,q=map(int,input().split())
s=input()
td=[list(input().split()) for _ in range(q)]
def func0(x):
  # はじめx(0-indexed)にいるゴーレムが0から左にいき消滅するか
  for t,d in td:
    if t==s[x]:
      if d=='R':x+=1
      if d=='L':x-=1
    if x<0:return True
    if x>n-1:return False
  return False
def funcN(x):
  # はじめx(0-indexed)にいるゴーレムがn-1から右にいき消滅するか
  for t,d in td:
    if t==s[x]:
      if d=='R':x+=1
      if d=='L':x-=1
    if x<0:return False
    if x>n-1:return True
  return False

l,r=-1,n
while r-l>1:
  x=(l+r)//2
  if func0(x):
    l,r=x,r
  else:
    l,r=l,x
a=l
l,r=-1,n
while r-l>1:
  x=(l+r)//2
  if funcN(x):
    l,r=l,x
  else:
    l,r=x,r
b=r
print(n-(a+1)-(n-b))
Buggy python submission (verdict: Time Limit Exceeded):
b,w=map(int,input().split())
dp=[0]*(b+w)
dp[0]=1/2
mod=pow(10,9)+7

def cmb(n,r,mod):
  if (r<0 or r>n):
    return 0
  r=min(r,n-r)
  return g1[n]*g2[r]*g2[n-r]%mod
g1=[1,1] # g1[i]=i! % mod　:階乗
g2=[1,1] # g2[i]=(i!)^(-1) % mod　:階乗の逆元
inverse=[0,1]
for i in range(2,b+w+1):
  g1.append((g1[-1]*i)%mod)
  inverse.append((-inverse[mod%i]*(mod//i))%mod)
  g2.append((g2[-1]*inverse[-1])%mod)
t1,t2=0,0
for i in range(1,1+b+w):
  t=pow(2,mod-2,mod)
  if i-b>0:
    t1*=2
    t1+=cmb(i-2,b-1,mod)
    tmp=t1*pow(2,mod-1-i,mod)
    tmp%=mod
    t-=tmp
    t%=mod
  if i-w>0:
    t2*=2
    t2+=cmb(i-2,w-1,mod)
    tmp=t2*pow(2,mod-1-i,mod)
    tmp%=mod
    t+=tmp
    t%=mod
  print(t)



Fixed submission:
b,w=map(int,input().split())
dp=[0]*(b+w)
dp[0]=1/2
mod=pow(10,9)+7

def cmb(n,r,mod):
  if (r<0 or r>n):
    return 0
  r=min(r,n-r)
  return g1[n]*g2[r]*g2[n-r]%mod
g1=[1,1] # g1[i]=i! % mod　:階乗
g2=[1,1] # g2[i]=(i!)^(-1) % mod　:階乗の逆元
inverse=[0,1]
for i in range(2,b+w+1):
  g1.append((g1[-1]*i)%mod)
  inverse.append((-inverse[mod%i]*(mod//i))%mod)
  g2.append((g2[-1]*inverse[-1])%mod)
t1,t2=0,0
for i in range(1,1+b+w):
  t=pow(2,mod-2,mod)
  if i-b>0:
    t1*=2
    t1%=mod
    t1+=cmb(i-2,b-1,mod)
    t1%=mod
    tmp=t1*pow(2,mod-1-i,mod)
    tmp%=mod
    t-=tmp
    t%=mod
  if i-w>0:
    t2*=2
    t2%=mod
    t2+=cmb(i-2,w-1,mod)
    t2%=mod
    tmp=t2*pow(2,mod-1-i,mod)
    tmp%=mod
    t+=tmp
    t%=mod
  print(t)

Buggy python submission (verdict: Time Limit Exceeded):
b,w=map(int,input().split())
dp=[0]*(b+w)
dp[0]=1/2
mod=pow(10,9)+7

def cmb(n,r,mod):
  if (r<0 or r>n):
    return 0
  r=min(r,n-r)
  return g1[n]*g2[r]*g2[n-r]%mod
g1=[1,1] # g1[i]=i! % mod　:階乗
g2=[1,1] # g2[i]=(i!)^(-1) % mod　:階乗の逆元
inverse=[0,1]
for i in range(2,b+w+1):
  g1.append((g1[-1]*i)%mod)
  inverse.append((-inverse[mod%i]*(mod//i))%mod)
  g2.append((g2[-1]*inverse[-1])%mod)

for i in range(1,1+b+w):
  t=pow(2,mod-2,mod)
  t1,t2=0,0
  if i-b>0:
    t1=sum([cmb(i-1,x,mod) for x in range(b,i+1)])%mod
    t1*=pow(2,mod-1-i,mod)
    t1%=mod
    t-=t1
    t%=mod
  if i-w>0:
    t2=sum([cmb(i-1,x,mod) for x in range(w,i+1)])%mod
    t2*=pow(2,mod-1-i,mod)
    t2%=mod
    t+=t2
    t%=mod
  print(t)



Fixed submission:
b,w=map(int,input().split())
dp=[0]*(b+w)
dp[0]=1/2
mod=pow(10,9)+7

def cmb(n,r,mod):
  if (r<0 or r>n):
    return 0
  r=min(r,n-r)
  return g1[n]*g2[r]*g2[n-r]%mod
g1=[1,1] # g1[i]=i! % mod　:階乗
g2=[1,1] # g2[i]=(i!)^(-1) % mod　:階乗の逆元
inverse=[0,1]
for i in range(2,b+w+1):
  g1.append((g1[-1]*i)%mod)
  inverse.append((-inverse[mod%i]*(mod//i))%mod)
  g2.append((g2[-1]*inverse[-1])%mod)
t1,t2=0,0
for i in range(1,1+b+w):
  t=pow(2,mod-2,mod)
  if i-b>0:
    t1*=2
    t1%=mod
    t1+=cmb(i-2,b-1,mod)
    t1%=mod
    tmp=t1*pow(2,mod-1-i,mod)
    tmp%=mod
    t-=tmp
    t%=mod
  if i-w>0:
    t2*=2
    t2%=mod
    t2+=cmb(i-2,w-1,mod)
    t2%=mod
    tmp=t2*pow(2,mod-1-i,mod)
    tmp%=mod
    t+=tmp
    t%=mod
  print(t)
Buggy python submission (verdict: Time Limit Exceeded):
n,q=map(int,input().split())
s=input()
lr=[]
for _ in range(q):
  lr.append(list(map(int,input().split())))
for i in range(q):
  t=s[lr[i][0]-1:lr[i][1]]
  print(t.count('AC'))


Fixed submission:
n,q=map(int,input().split())
s=input()
lr=[]
for _ in range(q):
  lr.append(list(map(int,input().split())))
sa=[0,0]
c=0
for i in range(1,n):
  if s[i-1]+s[i]=='AC':
    c+=1
  sa.append(c)
for i in range(q):
  t=sa[lr[i][1]]-sa[lr[i][0]]
  print(t)
Buggy python submission (verdict: Runtime Error):
n=int(input())
ans=[]
if n%2==0:
    for i in range(1,n):
        for j in range(i+1,n+1):
            if i+j!=n+1:
                ans.appned([i,j])
else:
    for i in range(1,n):
        for j in range(i+1,n+1):
            if i+j!=n:
                ans.appned([i,j])
print(len(ans))
for i,j in ans:
    print(i,j)


Fixed submission:
n=int(input())
ans=[]
if n%2==0:
    for i in range(1,n):
        for j in range(i+1,n+1):
            if i+j!=n+1:
                ans.append([i,j])
else:
    for i in range(1,n):
        for j in range(i+1,n+1):
            if i+j!=n:
                ans.append([i,j])
print(len(ans))
for i,j in ans:
    print(i,j)
Buggy python submission (verdict: Runtime Error):
n,k=map(int,input().split())
a=list(map(int,input().split()))
d={j:0 for j in range(32)}
for ai in a:
  for j in range(32):
    if (ai>>j) & 1:
      d[j]+=1
ans=0
l=len(bin(k))-3
import sys
sys.setrecursionlimit(10**7)

def dp(m,t): # 一番左の桁（l桁目）から考える。一番右の桁は0桁目。t:kより真に小さいかどうか
  if m<0:return 0
  ret=0
  if t==1: # 以降は好きに選んでいいので、最適な数字を選ぶ。一意。
    for i in range(m+1):
      tmp=max(0,n-2*d[i])
      ret+=pow(2,i)*tmp
  else:
    if (k>>m)&1: #kのm桁目が1なら1か0を選べる
      tmp1=dp(m-1,0)+(n-2*d[m])*pow(2,m)
      tmp0=dp(m-1,1)
      ret+=max(tmp1,tmp0)
    else:
      ret+=dp(m-1,0)
  return ret

print(sum(a)+dp(l,0))

Fixed submission:
n,k=map(int,input().split())
a=list(map(int,input().split()))
d={j:0 for j in range(41)}
for ai in a:
  for j in range(41):
    if (ai>>j) & 1:
      d[j]+=1
ans=0
l=len(bin(k))-3
import sys
sys.setrecursionlimit(10**7)

def dp(m,t): # 一番左の桁（l桁目）から考える。一番右の桁は0桁目。t:kより真に小さいかどうか
  if m<0:return 0
  ret=0
  if t==1: # 以降は好きに選んでいいので、最適な数字を選ぶ。一意。
    for i in range(m+1):
      tmp=max(0,n-2*d[i])
      ret+=pow(2,i)*tmp
  else:
    if (k>>m)&1: #kのm桁目が1なら1か0を選べる
      # 1にするとき
      tmp1=dp(m-1,0)+(n-2*d[m])*pow(2,m)
      # 0にするとき
      tmp0=dp(m-1,1)                    
      ret+=max(tmp1,tmp0)
    else:
      ret+=dp(m-1,0)
  return ret

print(sum(a)+dp(l,0))
Buggy python submission (verdict: Time Limit Exceeded):
n,m=map(int,input().split())
root_kouho=set(list(range(n)))
ki=[[] for _ in range(n)]
for i in range(n-1+m):
  a,b=map(int,input().split())
  a,b=a-1,b-1
  root_kouho.discard(b)
  ki[a].append(b)
root=root_kouho.pop()
p=[-1]*n
p[root]=0
todo=[[root,-1,0]]
ans=[-1]*n
ans[root]=0
seen=[0]*n
#todo=[[root,-1]]
while todo:
  t,p,d=todo.pop()
  for li in ki[t]:
    if li!=p:
      if seen[li]==-1 or seen[li]<d+1:
        ans[li]=t+1
        seen[li]=d+1
        todo.append([li,t,d+1])
print(*ans,sep='\n')

Fixed submission:
import sys
sys.setrecursionlimit(10**7)
n,m=map(int,input().split())
root_kouho=set(list(range(n)))
leaf=set(list(range(n)))
ki=[[] for _ in range(n)]
for i in range(n-1+m):
  a,b=map(int,input().split())
  a,b=a-1,b-1
  root_kouho.discard(b)
  leaf.discard(a)
  ki[b].append(a)
root=root_kouho.pop()
ans=[-1]*n
dp=[-1]*n # 根までの最長距離
ans[root]=0
dp[root]=0
def func(v):
  if dp[v]>=0:
    return dp[v]
  else:
    ret=-1
    for nv in ki[v]:
      tmp=func(nv)
      if ret<tmp:
        ret=tmp
        ans[v]=nv+1
    dp[v]=ret+1
    return ret+1
while leaf:
  l=leaf.pop()
  func(l)
print(*ans,sep='\n')
#print(dp)

Buggy python submission (verdict: Time Limit Exceeded):
n,m=map(int,input().split())
root_kouho=set(list(range(n)))
ki=[[] for _ in range(n)]
for i in range(n-1+m):
  a,b=map(int,input().split())
  a,b=a-1,b-1
  root_kouho.discard(b)
  ki[a].append(b)
root=root_kouho.pop()
from collections import deque
p=[-1]*n
p[root]=0
todo=deque([[root,-1]])
ans=[-1]*n
ans[root]=0
#todo=[[root,-1]]
while todo:
  t,p=todo.popleft()
  for li in ki[t]:
    if li!=p:
      ans[li]=t+1
      todo.append([li,t])
print(*ans,sep='\n')

Fixed submission:
import sys
sys.setrecursionlimit(10**7)
n,m=map(int,input().split())
root_kouho=set(list(range(n)))
leaf=set(list(range(n)))
ki=[[] for _ in range(n)]
for i in range(n-1+m):
  a,b=map(int,input().split())
  a,b=a-1,b-1
  root_kouho.discard(b)
  leaf.discard(a)
  ki[b].append(a)
root=root_kouho.pop()
ans=[-1]*n
dp=[-1]*n # 根までの最長距離
ans[root]=0
dp[root]=0
def func(v):
  if dp[v]>=0:
    return dp[v]
  else:
    ret=-1
    for nv in ki[v]:
      tmp=func(nv)
      if ret<tmp:
        ret=tmp
        ans[v]=nv+1
    dp[v]=ret+1
    return ret+1
while leaf:
  l=leaf.pop()
  func(l)
print(*ans,sep='\n')
#print(dp)
Buggy python submission (verdict: Runtime Error):
from collections import deque
n,k= map(int,input().split())
td=[]
for i in range(n):
    td.append(list(map(int,input().split())))
td.sort(key=lambda x:x[1],reverse=True)
select=[]
noselect=[]
cat=[]
for tdi in td:
    if tdi[0] in cat:
        noselect.append(tdi)
        continue
    select.append(tdi)
    cat.append(tdi[0])
    if len(select)==k:
        break
i=0
while len(select) < k:
    select.append(noselect[i])
    i+=1
noselect=noselect[i:]

print(8)


Fixed submission:
a,b,c=map(int,input().split())
print((a*b)//2)

Buggy python submission (verdict: Runtime Error):
"""
5 3
1 9
1 7
2 6
2 5
3 1
->26
7 4
1 1
2 1
3 1
4 6
4 5
4 5
4 5
->25
6 5
5 1000000000
2 990000000
3 980000000
6 970000000
6 960000000
4 950000000
->4900000016
"""

from collections import deque
n,k= map(int,input().split())
td=[]
for i in range(n):
    td.append(list(map(int,input().split())))
td.sort(key=lambda x:x[1],reverse=True)
select=[]
noselect=[]
cat=[]
for tdi in td:
    if tdi[0] in cat:
        noselect.append(tdi)
        continue
    select.append(tdi)
    cat.append(tdi[0])
    if len(select)==k:
        break
i=0
while len(select) < k:
    select.append(noselect[i])
    i+=1
noselect=noselect[i:]

select.sort(key=lambda x:x[1])
select=deque(select)
#cat=list(set([tdi[0] for tdi in select]))
for no in noselect:
    if no[0] not in cat:
        continue
    if (2 * len(cat)) - 1 < no[1] - select[0][1]:
        select.popleft()
        select.append(no)
        cat=list(set([tdi[0] for tdi in select]))
    else:
        break
print(sum([tdi[1] for tdi in select])+(len(cat)**2))


Fixed submission:
a,b,c=map(int,input().split())
print((a*b)//2)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
h,w=map(int,input().split())
s=[]
for _ in range(h):
    s.append(input())
ans=0
for x in range(h):
    for y in range(w):
        if s[x][y]=='.':
            continue
        path = deque([[x,y]])
        sc=[[0 for i in range(w)] for j in range(h)]
        sc[x][y]=1
        while len(path)>0:
            p = path.popleft()
            i,j=p[0],p[1]
            tc = '.' if s[i][j] == '#' else '#'
            point = 1 if s[i][j] == '#' else 0
            if i > 0 and s[i-1][j]==tc and sc[i-1][j]==0:
                sc[i-1][j]=1
                path.append([i-1,j])
                ans += point
            if j > 0 and s[i][j-1]==tc and sc[i][j-1]==0:
                sc[i][j-1]=1
                path.append([i,j-1])
                ans += point
            if i < h-1 and s[i+1][j]==tc and sc[i+1][j]==0:
                sc[i+1][j]=1
                path.append([i+1,j])
                ans += point
            if j < w-1 and s[i][j+1]==tc and sc[i][j+1]==0:
                sc[i][j+1]=1
                path.append([i,j+1])
                ans += point
#print(sc)
print(ans)

Fixed submission:

from collections import deque
h,w=map(int,input().split())
s=[]
for _ in range(h):
    s.append(input())
ans=0        
sc=[[0 for i in range(w)] for j in range(h)]

for x in range(h):
    for y in range(w):
        if s[x][y]=='.' or sc[x][y]==1:
            continue
        path = deque([[x,y]])
        sc[x][y]=1
        b=1
        wh=0
        while len(path)>0:
            p = path.popleft()
            i,j=p[0],p[1]
            tc = '.' if s[i][j] == '#' else '#'
            point = b if s[i][j] == '#' else wh           
            if i > 0 and s[i-1][j]==tc and sc[i-1][j]==0:
                sc[i-1][j]=1
                path.append([i-1,j])
                if s[i-1][j] == '#':
                    b += 1
                else:
                    wh += 1
                ans += point
            if j > 0 and s[i][j-1]==tc and sc[i][j-1]==0:
                sc[i][j-1]=1
                path.append([i,j-1])
                if s[i][j-1] == '#':
                    b += 1
                else:
                    wh += 1
                ans += point
            if i < h-1 and s[i+1][j]==tc and sc[i+1][j]==0:
                sc[i+1][j]=1
                path.append([i+1,j])
                if s[i+1][j] == '#':
                    b += 1
                else:
                    wh += 1
                ans += point
            if j < w-1 and s[i][j+1]==tc and sc[i][j+1]==0:
                sc[i][j+1]=1
                path.append([i,j+1])
                if s[i][j+1] == '#':
                    b += 1
                else:
                    wh += 1
                ans += point
print(ans)
Buggy python submission (verdict: Runtime Error):
import numpy as np
#n,k=map(int,input().split())
n=int(input())
abc=[]
for _ in range(n):
      abc.append(list(map(int,input().split())))
dp=np.zeros(n+1)
# dp[i]:i日目までの最大。dp[0]=0。求めるのはdp[n]
dp[1]=max(abc[0])
op1=[i for i in range(3) if abc[0][i]!=dp[1]]
if len(op1)<2:
      op1=[0,1,2]
op2=[0,1,2]
for i in range(2,n+1):
      m=max([abc[i-1][j] for j in op1])
      m1=dp[i-1]+m
      op=[j for j in range(3) if abc[i-1][j]!=m]
      if len(op)<2:
            op=[0,1,2]
      opt=[j for j in range(3) if abc[i-1][j]!=max(abc[i-1])]
      if len(op)<2:
            opt=[0,1,2]
      m2=dp[i-2]+max(abc[i-1])+max([abc[i-2][j] for j in set(op2).intersection(set(opt))])
      dp[i]=max(m1,m2)
      op2=op1
      op1=op

print(int(dp[-1]))

Fixed submission:
import numpy as np
n=int(input())
abc=[]
for _ in range(n):
      abc.append(list(map(int,input().split())))
dp=np.zeros((n+1,3),np.int64)
# dp[i][0]:i日目でaをとった時の最大。dp[0]=[0,0,0]。求めるのはmax(dp[n])
dp[1]=np.array(abc[0])
for i in range(2,n+1):
      dp[i][0]=abc[i-1][0]+max(dp[i-1][1],dp[i-1][2])
      dp[i][1]=abc[i-1][1]+max(dp[i-1][0],dp[i-1][2])
      dp[i][2]=abc[i-1][2]+max(dp[i-1][0],dp[i-1][1])

print(int(np.max(dp[-1])))