Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int, input().split()))
Ab = []
for i in range(N):
  Ab.append([A[i], i])
  
Ab.sort(reverse=True)
#dp[i][j] Aの大きいじゅんにi個とったとき、左寄せj個、右寄せi-j個としたときのMAX
dp = [[0 for _ in range(N+5)] for _ in range(N+5)]
dp[0][0] = 0

for i in range(0,N):
  a, p = Ab[i]
  for j in range(0,i+1):
    r = i - j
    dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j] + a * (p-j))
    dp[i+1][j]  = max(dp[i+1][j], dp[i][j] + a * (N-r-p-1))
                      
ans = 0
for i in range(N):
  ans = max(ans, dp[N][i])
  
print(ans)
#for a in dp:
#  print(a)
                       

Fixed submission:
N = int(input())
A = list(map(int, input().split()))
Ab = []
for i in range(N):
  Ab.append([A[i], i])
  
Ab.sort(reverse=True)
#dp[i][j] Aの大きいじゅんにi個とったとき、左寄せj個、右寄せi-j個としたときのMAX
dp = [[0 for _ in range(N+5)] for _ in range(N+5)]
dp[0][0] = 0

for i in range(0,N):
  a, p = Ab[i]
  for j in range(0,i+1):
    r = i - j
    dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j] + a * (p-j))
    dp[i+1][j]  = max(dp[i+1][j], dp[i][j] + a * (N-r-p-1))
                      
ans = 0
for i in range(N):
  ans = max(ans, dp[N][i])
  
print(ans)
#for a in dp:
#  print(a)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter
N = int(input())
A = []
for _ in range(N):
  A.append(input())

c = Counter(A)
l = [i[0] for i in c.items() if i[1] == c.most_common()[0][1]]
l.sort()

for s in l:
  print(s)

Fixed submission:
from collections import Counter
N = int(input())
A = []
for _ in range(N):
  A.append(input())

c = Counter(A)
maxcnt = c.most_common()[0][1]
l = []
for i in c.most_common():
  if i[1] != maxcnt:
    break
  l.append(i[0])

for s in sorted(l):
  print(s)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter
N = int(input())
A = []
for _ in range(N):
  A.append(input())

c = Counter(A)
l = [i[0] for i in c.items() if i[1] == c.most_common()[0][1]]
l.sort()

for s in l:
  print(s)

Fixed submission:
from collections import Counter
N = int(input())
A = []
for _ in range(N):
  A.append(input())

c = Counter(A)
maxcnt = c.most_common()[0][1]
l = []
for i in c.most_common():
  if i[1] != maxcnt:
    break
  l.append(i[0])

for s in sorted(l):
  print(s)
Buggy python submission (verdict: Time Limit Exceeded):
from math import ceil
H,N = list(map(int, input().split()))
A = []
for _ in range(N):
  A.append(list(map(int, input().split())))
  
# 1回iを使ってから、のこりをjで仕留める、を全探索でよい気がする
# だめだった

# dp[i] : HPをi減らすために必要なmin魔力
dp = [1e9] * (10010)
dp[0] = 0
for i in range(1,H+1):
  for a in A:
    ap, mp = a
    down = max(0, i - ap)
    dp[i] = min(dp[i], dp[down] + mp)
      
print(min(dp[H:]))

Fixed submission:
from math import ceil
H,N = list(map(int, input().split()))
A = []
for _ in range(N):
  A.append(list(map(int, input().split())))
  
# 1回iを使ってから、のこりをjで仕留める、を全探索でよい気がする
# だめだった

# dp[i] : HPをi減らすために必要なmin魔力
dp = [1e9] * (10010)
dp[0] = 0
for i in range(1,H+1):
  for a in A:
    ap, mp = a
    down = max(0, i - ap)
    dp[i] = min(dp[i], dp[down] + mp)
      
print(min(dp[H:]))

Buggy python submission (verdict: Time Limit Exceeded):
from math import ceil
H,N = list(map(int, input().split()))
A = []
for _ in range(N):
  A.append(list(map(int, input().split())))
  
# 1回iを使ってから、のこりをjで仕留める、を全探索でよい気がする
# だめだった

# dp[i] : HPをi減らすために必要なmin魔力
dp = [1e9] * (10010)
dp[0] = 0
for i in range(1,H+1):
  for a in A:
    ap, mp = a
    down = max(0, i - ap)
    dp[i] = min(dp[i], min(dp[down:i]) + mp)
      
print(dp[H])

Fixed submission:
from math import ceil
H,N = list(map(int, input().split()))
A = []
for _ in range(N):
  A.append(list(map(int, input().split())))
  
# 1回iを使ってから、のこりをjで仕留める、を全探索でよい気がする
# だめだった

# dp[i] : HPをi減らすために必要なmin魔力
dp = [1e9] * (10010)
dp[0] = 0
for i in range(1,H+1):
  for a in A:
    ap, mp = a
    down = max(0, i - ap)
    dp[i] = min(dp[i], dp[down] + mp)
      
print(min(dp[H:]))
Buggy python submission (verdict: Runtime Error):
N = int(input())

L = [0] * N

for i in range(N):
  A = int(input())
  #print(i)
  L[i] = [list(map(int, input().split()))]
  for j in range(1,A):
    L[i].append(list(map(int, input().split())))
    
#print(L)

ans = 0
for i in range(2**N):
  pat = str(format(i, '0' + str(N) + 'b'))
  flg = True
  #S = [-1] * (N)
  for j in range(N):
    if pat[j] == "1": # trueman
      for rule in L[j]:
        if pat[rule[0]-1] == "0" and rule[1] == 1:
          flg = False
          break
        if pat[rule[0]-1] == "1" and rule[1] == 0:
          flg = False
          break
  #print("XXX", flg, pat, j)
  if flg:
    work = 0
    for ch in pat:
      if ch == "1":
        work += 1
    #print("XXX", flg, pat, j, work)
    ans = max(ans, work)
    
print(ans)

Fixed submission:
N = int(input())

L = [0] * N

for i in range(N):
  A = int(input())
  if A == 0:
    L[i] = []
  else:
    L[i] = [list(map(int, input().split()))]
  for j in range(1,A):
    L[i].append(list(map(int, input().split())))
    
#print(L)

ans = 0
for i in range(2**N):
  pat = str(format(i, '0' + str(N) + 'b'))
  flg = True
  #S = [-1] * (N)
  for j in range(N):
    if pat[j] == "1": # trueman
      for rule in L[j]:
        if pat[rule[0]-1] == "0" and rule[1] == 1:
          flg = False
          break
        if pat[rule[0]-1] == "1" and rule[1] == 0:
          flg = False
          break
  #print("XXX", flg, pat, j)
  if flg:
    work = 0
    for ch in pat:
      if ch == "1":
        work += 1
    #print("XXX", flg, pat, j, work)
    ans = max(ans, work)
    
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from math import log, ceil
N = int(input())
A = list(map(int, input().split()))

#print(ceil(log(max(A)+1,2)))
keta = ceil(log(max(A)+1,2))

X = [0] * keta

for a in A:
  work = a
  i = 0
  while work > 0:
    X[i] += work % 2
    i += 1
    work = work // 2

ans = 0
mod = int(1e9+7)
for i in range(len(X)):
  ans += X[i] * (N-X[i]) * 2**i
  ans = ans % mod
  
print(ans)

Fixed submission:
from math import log, ceil
N = int(input())
A = list(map(int, input().split()))

#print(ceil(log(max(A)+1,2)))
keta = ceil(log(max(A)+1,2))

X = [0] * keta

for a in A:
  work = a
  i = 0
  while work > 0:
    X[i] += work % 2
    i += 1
    work = work // 2

ans = 0
mod = int(1e9+7)
for i in range(len(X)):
  ans += X[i] * (N-X[i]) * 2**i
  ans = ans % mod
  
print(ans)
Buggy python submission (verdict: Runtime Error):
import math
a,b,x = list(map(int, input().split()))

x = x / a

if x > a*b / 2:
  print(90 - math.degrees(math.atan(a*a/2/(a*b - x))))
else:
  print(90 - math.degrees(math.atan(2*x/b/b)))
  
  

Fixed submission:
import math
a,b,x = list(map(int, input().split()))

x = x / a

if a*b == x:
  print(0)
elif x > a*b / 2:
  print(90 - math.degrees(math.atan(a*a/2/(a*b - x))))
else:
  print(90 - math.degrees(math.atan(2*x/b/b)))
Buggy python submission (verdict: Time Limit Exceeded):
from math import ceil
N,K = list(map(int, input().split()))
A = list(map(int, input().split()))
F = list(map(int, input().split()))

A.sort(reverse=True)
F.sort()
wk = 0
for i in range(N):
  wk += A[i] * F[i]
#print(wk)

def is_ok(arg):
  # 条件を満たすかどうか？問題ごとに定義
  cnt = 0
  for i in range(N):
    a,f = A[i], F[i]   
    if a*f <= arg:
      continue
    else:
      #(a-k) * f <= arg
      # a - arg/f <= k
      cnt += ceil(a-arg/f)
  return cnt <= K

def meguru_bisect(ng, ok):
  '''
    初期値のng,okを受け取り,is_okを満たす最小(最大)のokを返す
    まずis_okを定義すべし
    ng ok は  とり得る最小の値-1 とり得る最大の値+1
    最大最小が逆の場合はよしなにひっくり返す
    '''
  while (abs(ok - ng) > 1):
    mid = (ok + ng) // 2
    if is_ok(mid):
      ok = mid
    else:
      ng = mid
  return ok

ng = -1
ok = 10**12 + 10
ans = meguru_bisect(ng,ok)

print(ans)

Fixed submission:
from math import ceil
N,K = list(map(int, input().split()))
A = list(map(int, input().split()))
F = list(map(int, input().split()))

A.sort(reverse=True)
F.sort()
wk = 0
for i in range(N):
  wk += A[i] * F[i]
#print(wk)

def is_ok(arg):
  # 条件を満たすかどうか？問題ごとに定義
  cnt = 0
  for i in range(N):
    a,f = A[i], F[i]   
    if a*f <= arg:
      continue
    else:
      #(a-k) * f <= arg
      # a - arg/f <= k
      cnt += ceil(a-arg/f)
  return cnt <= K

def meguru_bisect(ng, ok):
  '''
    初期値のng,okを受け取り,is_okを満たす最小(最大)のokを返す
    まずis_okを定義すべし
    ng ok は  とり得る最小の値-1 とり得る最大の値+1
    最大最小が逆の場合はよしなにひっくり返す
    '''
  while (abs(ok - ng) > 1):
    mid = (ok + ng) // 2
    if is_ok(mid):
      ok = mid
    else:
      ng = mid
  return ok

ng = -1
ok = 10**12 + 10
ans = meguru_bisect(ng,ok)

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import bisect

N = int(input())
L = list(map(int, input().split()))
L.sort()

ans = 0
# a <= b <= c

for b in range(1,N-1):
  for c in range(b+1,N):
    # search min(c) with a + b > c <=> a > c - b
    idx = bisect.bisect_left(L[:b],L[c]-L[b]+1)
    #print(L[b],L[c],idx)
    ans += max(b-idx,0) if idx >= 0 else 0 
    #print(idx, ans)
#print(L)
print(ans)

Fixed submission:
import bisect

N = int(input())
L = list(map(int, input().split()))
L.sort()

ans = 0
# a <= b <= c

for b in range(1,N-1):
  for c in range(b+1,N):
    # search min(c) with a + b > c <=> a > c - b
    idx = bisect.bisect_left(L[:b],L[c]-L[b]+1)
    #print(L[b],L[c],idx)
    ans += max(b-idx,0) if idx >= 0 else 0 
    #print(idx, ans)
#print(L)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
N = int(input())
S = []
for _ in range(N):
  S.append(input())
  
G = [[] for _ in range(N)]
for i in range(N):
  for j in range(i+1,N):
    if S[i][j] == '1':
      G[i].append(j)
      G[j].append(i)

# 2部グラフ判定
visited = [False] * N
willSearch = [False] * N
Color = [-1] * N
Q = deque()
Q.append((0,0))
while Q:
  now, c = Q.pop()
  visited[now] = True
  Color[now] = c
  for nxt in G[now]:
    if Color[nxt] >= 0 and c == Color[nxt]:
      #隣接色が一致してしまった
      print(-1)
      exit(0)
    if visited[nxt] or willSearch[nxt]:
      continue
    Q.append((nxt,1-c)) # 1-cで0/1を交換
    willSearch[nxt] = True
    
INF = 1000
D = [[INF for _ in range(N) ]  for _ in range(N)]
for i in range(N):
  for nxt in G[i]:
    D[i][nxt] = 1
    D[nxt][i] = 1
    
#Warshall-Floyd
for k in range(N):
  for i in range(N):
    for j in range(N):
      #print(i,j,k)
      D[i][j] = min(D[i][j], D[i][k] + D[k][j])
      
#print(*D, sep="\n")

ans = 0
for i in range(N):
  for j in range(i+1,N):
    ans = max(ans, D[i][j])
    
print(ans+1)

Fixed submission:
from collections import deque
N = int(input())
S = []
for _ in range(N):
  S.append(input())
  
G = [[] for _ in range(N)]
for i in range(N):
  for j in range(i+1,N):
    if S[i][j] == '1':
      G[i].append(j)
      G[j].append(i)

# 2部グラフ判定
visited = [False] * N
willSearch = [False] * N
Color = [-1] * N
Q = deque()
Q.append((0,0))
while Q:
  now, c = Q.pop()
  visited[now] = True
  Color[now] = c
  for nxt in G[now]:
    if Color[nxt] >= 0 and c == Color[nxt]:
      #隣接色が一致してしまった
      print(-1)
      exit(0)
    if visited[nxt] or willSearch[nxt]:
      continue
    Q.append((nxt,1-c)) # 1-cで0/1を交換
    willSearch[nxt] = True
    
INF = 1000
D = [[INF for _ in range(N) ]  for _ in range(N)]
for i in range(N):
  for nxt in G[i]:
    D[i][nxt] = 1
    D[nxt][i] = 1
    
#Warshall-Floyd
for k in range(N):
  for i in range(N):
    for j in range(N):
      #print(i,j,k)
      D[i][j] = min(D[i][j], D[i][k] + D[k][j])
      
#print(*D, sep="\n")

ans = 0
for i in range(N):
  for j in range(i+1,N):
    ans = max(ans, D[i][j])
    
print(ans+1)
Buggy python submission (verdict: Time Limit Exceeded):
n,m = list(map(int,input().split()))

dp = [1e9 for _ in range(2**n)]
#dp[status]
# status : c1c2c3...を開けることができる=1としたときの2進⇒10進数(maxは1がnこ並ぶから2**n -1)
dp[0] = 0
for i in range(1,m+1):
  a, _ = list(map(int,input().split()))
  C = list(map(int,input().split()))
  s = sum([2**(c-1) for c in C]) ## 内包forできれいに書いてる
  for j in range(2**n): ## ひとつ前のステータスを総当たりでいく
    dp[j|s] = min(dp[j|s], dp[j] + a)  ## このorの書き方が美しいのか

ans = dp[2**n-1] # 全部のカギを使ったときのstatusがすべて1の時
print(ans if ans < 1e9 else -1)

Fixed submission:
n,m = list(map(int,input().split()))

dp = [1e9 for _ in range(2**n)]
#dp[status]
# status : c1c2c3...を開けることができる=1としたときの2進⇒10進数(maxは1がnこ並ぶから2**n -1)
dp[0] = 0
for i in range(1,m+1):
  a, _ = list(map(int,input().split()))
  C = list(map(int,input().split()))
  s = sum([2**(c-1) for c in C]) ## 内包forできれいに書いてる
  for j in range(2**n): ## ひとつ前のステータスを総当たりでいく
    dp[j|s] = min(dp[j|s], dp[j] + a)  ## このorの書き方が美しいのか

ans = dp[2**n-1] # 全部のカギを使ったときのstatusがすべて1の時
print(ans if ans < 1e9 else -1)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = input()

# 左は尺取り。しかも３とって失敗したら、l,r双方いんくりしてよい
# 右は総当たり。

ans = 0
l,r = 0,1
while l<N and r<N:
  findf = False
  target = S[l:r]
  L = r-l
  for k in range(l+L,N-1):
    compare = S[k:k+L]
    #print(target, compare)
    if target == S[k:k+L]:
      ans = max(ans,L)
      findf = True
      break
  if findf and r < N-1:
    r += 1
  else:
    l += 1
    r = min(r+1,N-1)
    
print(ans)

Fixed submission:
N = int(input())
S = input()

# 左は尺取り。しかも３とって失敗したら、l,r双方いんくりしてよい
# 右は総当たり。

ans = 0
l,r = 0,1
while l<N and r<N:
  findf = False
  target = S[l:r]
  L = r-l
  for k in range(l+L,N-1):
    compare = S[k:k+L]
    #print(target, compare)
    if target == S[k:k+L]:
      ans = max(ans,L)
      findf = True
      break
  if findf and r < N-1:
    r += 1
  else:
    l += 1
    r = min(r+1,N-1)
    
print(ans)
Buggy python submission (verdict: Runtime Error):
S = input()
T = input()

ans = 0
for i in len(S):
  if S[i] == T[i]:
    ans += 1
    
print(ans)

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

ans = 0
for i in range(len(S)):
  if S[i] == T[i]:
    ans += 1
    
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
from collections import deque

N, Q = list(map(int, input().split()))
E = {}

# change limit for deep tree (recursion)
sys.setrecursionlimit(int(2e5+10))

for i in range(N-1):
  a,b = list(map(int, input().split()))
  a,b = a-1,b-1 # 1-indexed -> 0-indexed
  if a not in E:
    E[a] = [b]
  else:
    E[a].append(b)
  if b not in E:
    E[b] = [a]
  else:
    E[b].append(a)

P = [0] * N
for i in range(Q):
  a,b= list(map(int, input().split()))
  P[a-1] += b # 1-indexed -> 0-indexed
  
#print(E)
#print(P)

visited = [False for i in range(N)]
d = deque()

d.append(0)
while len(d) > 0:
  parent = d.pop()
  visited[parent] = True
  
  next_point = E[parent]
  
  for child in next_point:
    if visited[child]:
      continue
    P[child] += P[parent]
    d.append(child)
  
print(" ".join(list(map(str,P))))

Fixed submission:
import sys
from collections import deque

N, Q = list(map(int, input().split()))
E = {}

# change limit for deep tree (recursion)
sys.setrecursionlimit(int(2e5+10))

for i in range(N-1):
  a,b = list(map(int, input().split()))
  a,b = a-1,b-1 # 1-indexed -> 0-indexed
  if a not in E:
    E[a] = [b]
  else:
    E[a].append(b)
  if b not in E:
    E[b] = [a]
  else:
    E[b].append(a)

P = [0] * N
for i in range(Q):
  a,b= list(map(int, input().split()))
  P[a-1] += b # 1-indexed -> 0-indexed
  
#print(E)
#print(P)

visited = [False for i in range(N)]
d = deque()

d.append(0)
while len(d) > 0:
  parent = d.pop()
  visited[parent] = True
  
  next_point = E[parent]
  
  for child in next_point:
    if visited[child]:
      continue
    P[child] += P[parent]
    d.append(child)
  
print(" ".join(list(map(str,P))))
Buggy python submission (verdict: Runtime Error):
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (int)(n); ++i)
using namespace std;
using ll = long long;
using P = pair<int,int>;
//using T = tuple<string, int, int>;

int main() {
  int A,B,C;
  cin >> A >> B >> C;
  cout << max(C-(A-B), 0) << endl;

  return 0;
}

// https://github.com/atcoder/live_library

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

print(max(0,B+C-A))
Buggy python submission (verdict: Runtime Error):
from collections import Counter
N = int(input())
X = []
for _ in range(N):
  X.append(list(map(int, input().split())))
  
A = []
for i in range(N):
  for j in range(i+1,N):
    A.append((abs(X[i][0]-X[j][0]), abs(X[i][1]-X[j][1])))
    
C = Counter(A)
print(N - C.most_common()[0][1])

Fixed submission:
from collections import Counter
N = int(input())
X = []
for _ in range(N):
  X.append(list(map(int, input().split())))
  
if N == 1:
  print(1)
  exit(0)
A = []
for i in range(N):
  for j in range(N):
    if i==j:
      continue
    A.append((X[i][0]-X[j][0], X[i][1]-X[j][1]))
    
C = Counter(A)
print(N - C.most_common()[0][1])
Buggy python submission (verdict: Time Limit Exceeded):
MOD = int(1e9 + 7)

N,M = list(map(int, input().split()))
A = []
for i in range(M):
  A.append(int(input()))
  
for i in range(M-1):
  if A[i+1] - A[i] == 1:
    print(0)
    exit(0)
    
dp = [0] * (N+1)
dp[0] = 1
for i in range(N):
  if i-1 < 0 or i-1 in A:
    dp[i+1] = dp[i] % MOD
  elif i in A:
    dp[i+1] = dp[i-1] % MOD
  else:
    dp[i+1] = (dp[i] + dp[i-1]) % MOD
    
print(dp[N])

Fixed submission:
MOD = int(1e9 + 7)

N,M = list(map(int, input().split()))
A = list()
for i in range(M):
  A.append(int(input()))

A.sort(reverse=True)

for i in range(M-1):
  if A[i+1] - A[i] == 1:
    print(0)
    exit(0)
  
dp = [0] * (N+1)
dp[0] = 1
for i in range(N):
  if len(A) > 0 and i+1 == A[-1]:
    A.pop()
  else:  
    dp[i+1] = (dp[i] + dp[i-1]) % MOD
'''
  if len(A) < 1:
    dp[i+1] = (dp[i] + dp[i-1]) % MOD
  elif i-1 < 0 or i-1 == A[-1]:
    dp[i+1] = dp[i] % MOD
  elif i == A[-1]:
    dp[i+1] = dp[i-1] % MOD
  else:
    dp[i+1] = (dp[i] + dp[i-1]) % MOD
'''
print(dp[N])
#print(dp)
Buggy python submission (verdict: Runtime Error):
N = int(input())
V = {}
if N == 1:
  print(0)
  exit(0)

# Vertice
for i in range(N-1):
  u,v,w = list(map(int, input().split()))
  u,v = u-1, v-1 #1-index -> 0-index
  if u not in V:
    V[u] = [[v,w]]
  else:
    V[u].append([v,w])
  if v not in V:
    V[v] = [[u,w]]
  else:
    V[v].append([u,w])
     
#print(V)
ANS = [-1] * N
visited = [False] * N

def dfs(pos):
  visited[pos] = True
  for x,w in V[pos]:
    if visited[x]:
      continue
    if w % 2 == 0:
      ANS[x] = ANS[pos]
    else:
      ANS[x] = 1 - ANS[pos]
    #print(pos,x,ANS)
    dfs(x)
  return

ANS[0] = 0
dfs(0)

for a in ANS:
  print(a)

Fixed submission:
import sys
N = int(input())
V = {}
if N == 1:
  print(0)
  exit(0)

# change limit for deep tree (recursion)
sys.setrecursionlimit(N)

# Vertice
for i in range(N-1):
  u,v,w = list(map(int, input().split()))
  u,v = u-1, v-1 #1-index -> 0-index
  if u not in V:
    V[u] = [[v,w]]
  else:
    V[u].append([v,w])
  if v not in V:
    V[v] = [[u,w]]
  else:
    V[v].append([u,w])
     
#print(V)
ANS = [-1] * N
visited = [False] * N

def dfs(pos):
  visited[pos] = True
  for x,w in V[pos]:
    if visited[x]:
      continue
    if w % 2 == 0:
      ANS[x] = ANS[pos]
    else:
      ANS[x] = 1 - ANS[pos]
    #print(pos,x,ANS)
    dfs(x)
  return

ANS[0] = 0
dfs(0)

for a in ANS:
  print(a)

Buggy python submission (verdict: Runtime Error):
N = int(input())
V = {}

# Vertice
for i in range(N-1):
  u,v,w = list(map(int, input().split()))
  u,v = u-1, v-1 #1-index -> 0-index
  if u not in V:
    V[u] = [[v,w]]
  else:
    V[u].append([v,w])
  if v not in V:
    V[v] = [[u,w]]
  else:
    V[v].append([u,w])
     
#print(V)
ANS = [-1] * N
visited = [False] * N

def dfs(pos):
  visited[pos] = True
  for x,w in V[pos]:
    if visited[x]:
      continue
    if w % 2 == 0:
      ANS[x] = ANS[pos]
    else:
      ANS[x] = 1 - ANS[pos]
    #print(pos,x,ANS)
    dfs(x)
  return

ANS[0] = 0
dfs(0)

for a in ANS:
  print(a)

Fixed submission:
import sys
N = int(input())
V = {}
if N == 1:
  print(0)
  exit(0)

# change limit for deep tree (recursion)
sys.setrecursionlimit(N)

# Vertice
for i in range(N-1):
  u,v,w = list(map(int, input().split()))
  u,v = u-1, v-1 #1-index -> 0-index
  if u not in V:
    V[u] = [[v,w]]
  else:
    V[u].append([v,w])
  if v not in V:
    V[v] = [[u,w]]
  else:
    V[v].append([u,w])
     
#print(V)
ANS = [-1] * N
visited = [False] * N

def dfs(pos):
  visited[pos] = True
  for x,w in V[pos]:
    if visited[x]:
      continue
    if w % 2 == 0:
      ANS[x] = ANS[pos]
    else:
      ANS[x] = 1 - ANS[pos]
    #print(pos,x,ANS)
    dfs(x)
  return

ANS[0] = 0
dfs(0)

for a in ANS:
  print(a)
Buggy python submission (verdict: Time Limit Exceeded):
R,G,B,N = list(map(int, input().split()))

B,G,R = sorted([R,G,B])

ans = 0
for r in range(N//R + 1):
  for g in range(N//G + 1):
    if r*R + g*G > N:
      break
    if (N - r*R - g*G) % B == 0:
      ans += 1
      
print(ans)


Fixed submission:
R,G,B,N = list(map(int, input().split()))

B,G,R = sorted([R,G,B])

ans = 0
for r in range(N//R + 1):
  for g in range(N//G + 1):
    if r*R + g*G > N:
      break
    if (N - r*R - g*G) % B == 0:
      ans += 1
      
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from math import sqrt
N = int(input())
ans = 0
# if N // i = p, N % i = p, 
# N = pi + p = p(i+1)
# p < sqrt(N) and p < i 
for p in range(1,N):
  if N % p > 0:
    continue
  i = N//p - 1
  if p >= i:
    break
  ans += i
    
print(ans)

Fixed submission:
from math import sqrt
N = int(input())
ans = 0
# if N // i = p, N % i = p, 
# N = pi + p = p(i+1)
# p < sqrt(N) and p < i 
for p in range(1,N):
  if p > N/p - 1:
    break
  if N % p > 0:
    continue
  i = N//p - 1
  if p >= i:
    break
  ans += i
    
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque

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

A = []
for i in range(H):
  A.append(input())
  
Q = deque()
visited = [[False for i in range(W)] for j in range(H)]

for i in range(H):
  for j in range(W):
    if A[i][j] == '#':
      Q.append([i,j,0])
      visited[i][j] = True

ans = 0
while len(Q) > 0:
  i,j,dist = Q.popleft()
  for dy, dx in [[1,0], [-1,0], [0,-1], [0,1]]:
    y = i + dy
    x = j + dx
    if y < 0 or H <= y or x < 0 or W <= x:
      continue
    if visited[y][x]:
      continue
    visited[y][x] = True
    Q.append([y,x,dist+1])
    ans = max(ans, dist+1)
    
print(ans)


Fixed submission:
from collections import deque

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

A = []
for i in range(H):
  A.append(input())
  
Q = deque()
visited = [[False for i in range(W)] for j in range(H)]

for i in range(H):
  for j in range(W):
    if A[i][j] == '#':
      Q.append([i,j,0])
      visited[i][j] = True

ans = 0
while len(Q) > 0:
  i,j,dist = Q.popleft()
  for dy, dx in [[1,0], [-1,0], [0,-1], [0,1]]:
    y = i + dy
    x = j + dx
    if y < 0 or H <= y or x < 0 or W <= x:
      continue
    if visited[y][x]:
      continue
    visited[y][x] = True
    Q.append([y,x,dist+1])
    ans = max(ans, dist+1)
    
print(ans)
Buggy python submission (verdict: Runtime Error):
N, M, C = map(int, input().split())
B = list(map(int, input().split()))

ans = 0

for i in range(N):
  work = C
  for j in range(M):
    work += A[j] * B[j]
  if work >= 0:
    ans += 1
    
print(ans)

Fixed submission:
N, M, C = map(int, input().split())
B = list(map(int, input().split()))

ans = 0

for i in range(N):
  A = list(map(int, input().split()))
  work = C
  for j in range(M):
    work += A[j] * B[j]
  if work > 0:
    ans += 1
    
print(ans)
Buggy python submission (verdict: Runtime Error):
A, B, C = map(int, input.split())
print(min(B//A, C))

Fixed submission:
A, B, C = map(int, input().split())
print(min(B//A, C))
Buggy python submission (verdict: Time Limit Exceeded):
from functools import reduce

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

from functools import reduce

def gcd(a, b):
    if a<b:
      a,b = b,a
    while b != 0:
        a, b = b, a % b
    return a

def lcm(a, b):
    return (a * b) // gcd(a, b)

G,L = A[0], 1
for i in range(N-1):
  G = gcd(G,A[i+1])
  L = L * A[i+1] // G
  #print(G,L)
  
print(G)

Fixed submission:
from fractions import gcd

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

'''
def gcd(a, b):
    if a<b:
      a,b = b,a
    while b != 0:
        a, b = b, a % b
    return a
'''

G = A[0]
for i in range(N-1):
  G = gcd(G,A[i+1])
  
print(G)