Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
import sys
from itertools import accumulate


def input():
    return sys.stdin.readline().strip()


sys.setrecursionlimit(10 ** 9)


def main():
    N = int(input())
    S = input()
    ans = 0

    def find(a, b, c):
        for j in range(N - 2):
            if int(S[j]) == a:
                for k in range(j + 1, N - 1):
                    if int(S[k]) == b:
                        for l in range(k + 1, N):
                            if int(S[l]) == c:
                                return 1
        return 0

    for i in range(1000):
        a = i // 100
        b = (i % 100) // 10
        c = i % 10
        ans += find(a, b, c)

    print(ans)


if __name__ == "__main__":
    main()


Fixed submission:
import sys


def input():
    return sys.stdin.readline().strip()


sys.setrecursionlimit(10 ** 9)


def main():
    N = int(input())
    S = list(input())
    left_index = [[-1] * (N + 1) for _ in range(10)]
    for i, x in enumerate(S, 1):
        for j in range(10):
            left_index[j][i] = left_index[j][i - 1]
        left_index[ord(x) - ord("0")][i] = i
    answer = 0
    for i in range(1000):
        a = i // 100
        b = (i % 100) // 10
        c = i % 10
        j = N
        bl = True
        for x in [c, b, a]:
            j = left_index[x][j] - 1
            if j < -1:
                bl = False
                break
        if bl:
            answer += 1
    print(answer)


if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
from itertools import accumulate


def input():
    return sys.stdin.readline().strip()


sys.setrecursionlimit(10 ** 9)


def main():
    N = int(input())
    S = input()
    ans = 0

    def find(a, b, c):
        for j in range(N - 2):
            if int(S[j]) == a:
                for k in range(j + 1, N - 1):
                    if int(S[k]) == b:
                        for l in range(k + 1, N):
                            if int(S[l]) == c:
                                return 1
        return 0

    for i in range(1000):
        a = i // 100
        b = (i % 100) // 10
        c = i % 10
        ans += find(a, b, c)

    print(ans)


if __name__ == "__main__":
    main()


Fixed submission:
import sys


def input():
    return sys.stdin.readline().strip()


sys.setrecursionlimit(10 ** 9)


def main():
    N = int(input())
    S = list(input())
    left_index = [[-1] * (N + 1) for _ in range(10)]
    for i, x in enumerate(S, 1):
        for j in range(10):
            left_index[j][i] = left_index[j][i - 1]
        left_index[ord(x) - ord("0")][i] = i
    answer = 0
    for i in range(1000):
        a = i // 100
        b = (i % 100) // 10
        c = i % 10
        j = N
        bl = True
        for x in [c, b, a]:
            j = left_index[x][j] - 1
            if j < -1:
                bl = False
                break
        if bl:
            answer += 1
    print(answer)


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Runtime Error):
n=int(input())
A=list(map(int,input().split()))
S=sum(A)//2
cnt=0
i=0
while cnt<S:
    cnt+=A[i]
    i+=1
ans1=abs(cnt-sum(A[i:]))
ans2=abs(cnt+A[i]-sum(A[i+1:]))
print(min(ans1,ans2))

Fixed submission:
from itertools import accumulate
import sys
n=int(input())
A=list(map(int,input().split()))
S=sum(A)/2
B=list(accumulate(A))

for i in range(n):
    B[i]-=S
    if B[i]<0:
        continue
    elif B[i]==0:
        print(0)
        sys.exit()
    else:
        if i==0:
            print(A[0]-A[1:])
        elif i>0 and i<n-1:
            a=abs(sum(A[:i])-sum(A[i:]))
            b=abs(sum(A[:i+1])-sum(A[i+1:]))
            print(min(a,b))
        else:
            print(A[n-1]-sum(A[:n-1]))
        sys.exit()
Buggy python submission (verdict: Runtime Error):
import sys
n=int(input())
L=[]
for i in range(1,int(n**(1/2))):
    if n//i == n/i:
        L.append(n//i+i-2)
print(min(L))

Fixed submission:
import sys
n=int(input())
L=[]
for i in range(1,int(n**(1/2))+1):
    if n//i == n/i:
        L.append(n//i+i-2)
print(min(L))
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
L = sorted(list(map(int,input().split())),reverse= True)
cnt = 0
for i in range(n-2):
    for j in range(i+1,n-1):
        m = n-1
        M = j+1
        while M <= m:
            if L[i] < L[(m+M)//2]+L[j]:
                cnt += (m+M)//2-M+1
                M = (m+M)//2+1
            else:
                m = (m+M)//2-1

print(cnt)




Fixed submission:
import bisect
n = int(input())
L = list(map(int,input().split()))
L.sort()

ans = 0

for i in range(n-1):
    for j in range(i+1,n):
        index = bisect.bisect_left(L,L[i]+L[j])
        ans += index - (j+1)

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
L = sorted(list(map(int,input().split())),reverse= True)
cnt = 0
for i in range(n-2):
    for j in range(i+1,n-1):
        for k in range(j+1,n):
            if L[k]+L[j]>L[i]:
                cnt += 1
print(cnt)



Fixed submission:
import bisect
n = int(input())
L = list(map(int,input().split()))
L.sort()

ans = 0

for i in range(n-1):
    for j in range(i+1,n):
        index = bisect.bisect_left(L,L[i]+L[j])
        ans += index - (j+1)

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n,m = map(int,input().split())
A = list(map(int,input().split()))
for i in range(m):
    k = A.index(max(A))
    A[k] //= 2
print(sum(A))


Fixed submission:
import heapq
n,m = map(int,input().split())
A = list(map(lambda x:int(x)*(-1),input().split()))
heapq.heapify(A)

for i in range(m):
    tmp_min = heapq.heappop(A)
    heapq.heappush(A, (-1)*(-tmp_min//2))
print(-sum(A))
Buggy python submission (verdict: Time Limit Exceeded):
n,q=map(int,input().split())
node=[0 for i in range(n)]
tree=[]
for i in range(n-1):
    tree.append(list(map(int,input().split())))
def counter(p,x,cnt):
    for i in range(n-1):
        if tree[i][0]==p:
            if cnt[tree[i][1]-1]!=1:
                node[tree[i][1]-1]+=x
                cnt[tree[i][1]-1]=1
                counter(tree[i][1],x,cnt)
            else:
                continue
        
        
for j in range(q):
    cnt=[0 for i in range(n)]
    p,x=map(int,input().split())
    cnt[p-1]=1
    node[p-1]+=x
    counter(p,x,cnt)

for i in range(n):
    node[i]=str(node[i])
print(' '.join(node))




Fixed submission:
n,q=map(int,input().split())
c=[0 for i in range(n)]
tree=sorted([list(map(int,input().split())) for i in range(n-1)])
for j in range(q):
    p,x=map(int,input().split())
    c[p-1]+=x
for i in range(n-1):
    c[tree[i][1]-1]+=c[tree[i][0]-1]
for i in range(n):
    c[i]=str(c[i])
print(' '.join(c))
Buggy python submission (verdict: Time Limit Exceeded):
import sys


def input():
    return sys.stdin.readline().strip()


sys.setrecursionlimit(20000000)


def main():
    S = input()
    MOD = 10 ** 9 + 7
    dp = [[0] * 13 for _ in range(len(S) + 1)]
    dp[0][0] = 1
    mul = 1
    for i in range(len(S)):
        x = S[-(i + 1)]
        if x == "?":
            for k in range(10):
                for j in range(13):
                    dp[i + 1][(mul * k + j) % 13] += dp[i][j]
                    dp[i + 1][(mul * k + j) % 13] %= MOD
        else:
            k = int(x)
            for j in range(13):
                dp[i + 1][(mul * k + j) % 13] += dp[i][j]
                dp[i + 1][(mul * k + j) % 13] %= MOD
        mul = mul * 10 % 13
    print(dp[len(S)][5])


if __name__ == "__main__":
    main()


Fixed submission:
import sys


def input():
    return sys.stdin.readline().strip()


sys.setrecursionlimit(20000000)


def main():
    S = input()
    MOD = 10 ** 9 + 7
    dp = [[0] * 13 for _ in range(len(S) + 1)]
    dp[0][0] = 1
    mul = 1
    for i in range(len(S)):
        x = S[-(i + 1)]
        if x == "?":
            for k in range(10):
                for j in range(13):
                    dp[i + 1][(mul * k + j) % 13] += dp[i][j]
                    dp[i + 1][(mul * k + j) % 13] %= MOD
        else:
            k = int(x)
            for j in range(13):
                dp[i + 1][(mul * k + j) % 13] += dp[i][j]
                dp[i + 1][(mul * k + j) % 13] %= MOD
        mul = mul * 10 % 13
    print(dp[len(S)][5])


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Runtime Error):
n=int(input())
a=list(map(int,input().split()))
b=list(set(a))
if n%3!=0:
    print('No')
else:
    if b[0]^b[1]!=b[2]:
        print('No')
    elif a.count(b[0])==a.count(b[1])==a.count(b[2]):
        print('Yes')
    else:
        print('No')

Fixed submission:
n=int(input())
a=list(map(int,input().split()))
b=list(set(a))
if len(b)==1 and b[0]==0:
    print('Yes')
elif len(b)==2 and min(b)==0:
    b.sort()
    if n%3==0:
        if a.count(b[0])*2==a.count(b[1]):
            print('Yes')
        else:
            print('No')
    else:
        print('No')
elif n%3!=0:
    print('No')
else:
    if len(b)!=3:
        print('No')
    elif b[0]^b[1]==b[2]:
        if a.count(b[0])==a.count(b[1])==a.count(b[2]):
            print('Yes')
        else:
            print('No')
    else:
        print('No')
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
a=list(map(int,input().split()))
S=sum(a)
ans=[]
for i in range(n):
    rmv=0
    for j in range(n//2):
        k=(i+2*j+1)%(n)
        rmv+=a[k]
    ans.append(str(S-rmv*2))
print(' '.join(ans))



Fixed submission:
n=int(input())
a=list(map(int,input().split()))
ans=[]
b_1=0
for i in range(n):
    if i%2==0:
        b_1+=a[i]
    else:
        b_1-=a[i]
ans.append(str(b_1))
for i in range(1,n):
    ans.append(str(a[i-1]*2-int(ans[-1])))
print(' '.join(ans))

Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
a=list(map(int,input().split()))
S=sum(a)
for i in range(n):
    a[i]*=2
ans=[]
for i in range(n):
    rmv=0
    for j in range(n//2):
        k=(i+2*j+1)%(n)
        rmv+=a[k]
    ans.append(S-rmv)
for i in range(n):
    ans[i]=str(ans[i])
print(' '.join(ans))


Fixed submission:
n=int(input())
a=list(map(int,input().split()))
ans=[]
b_1=0
for i in range(n):
    if i%2==0:
        b_1+=a[i]
    else:
        b_1-=a[i]
ans.append(str(b_1))
for i in range(1,n):
    ans.append(str(a[i-1]*2-int(ans[-1])))
print(' '.join(ans))
Buggy python submission (verdict: Time Limit Exceeded):
n,m=map(int,input().split())
a=[int(input()) for _ in range(m)]
dp=[1]+[0 for _ in range(n)]
mod=1000000007
for i in range(1,n+1):
    if i in a:
        dp[i]=0
    else:
        dp[i]=(dp[i-1]+dp[i-2])%mod
print(dp[-1])

Fixed submission:
n,m=map(int,input().split())
a=[]
mod=1000000007
for _ in range(m):
    a.append(int(input()))
a=set(a)
ans=[1]+[0]*(n)
for i in range(1,n+1):
    if i in a:
        ans[i]=0
    else:
        ans[i]=(ans[i-1]+ans[i-2])%mod
print(ans[n])

Buggy python submission (verdict: Time Limit Exceeded):
n,m=map(int,input().split())
a=[int(input()) for _ in range(m)]
dp=[0 for _ in range(n+1)]
dp[0]=1
for i in range(1,n+1):
    if i in a:
        dp[i]=0
    else:
        dp[i]=(dp[i-1]+dp[i-2])%1000000007
print(dp[-1])

Fixed submission:
n,m=map(int,input().split())
a=[]
mod=1000000007
for _ in range(m):
    a.append(int(input()))
a=set(a)
ans=[1]+[0]*(n)
for i in range(1,n+1):
    if i in a:
        ans[i]=0
    else:
        ans[i]=(ans[i-1]+ans[i-2])%mod
print(ans[n])

Buggy python submission (verdict: Time Limit Exceeded):
n,m=map(int,input().split())
a=[int(input()) for _ in range(m)]
dp=[-1 for _ in range(n+1)]
dp[0]=dp[1]=1
def step(s):
    if s in a:
        dp[s]=0
        return
    elif dp[s]>=0:
        return 
    else:
        dp[s]=(dp[s-1]+dp[s-2])%1000000007
        return
for i in range(n+1):
    step(i)
print(dp[-1])

Fixed submission:
n,m=map(int,input().split())
a=[]
mod=1000000007
for _ in range(m):
    a.append(int(input()))
a=set(a)
ans=[1]+[0]*(n)
for i in range(1,n+1):
    if i in a:
        ans[i]=0
    else:
        ans[i]=(ans[i-1]+ans[i-2])%mod
print(ans[n])

Buggy python submission (verdict: Time Limit Exceeded):
n,m=map(int,input().split())
a=[int(input()) for _ in range(m)]
dp=[-1 for _ in range(n+1)]
dp[0]=dp[1]=1
def step(s):
    if s in a:
        dp[s]=0
        return
    elif dp[s]>=0:
        return 
    else:
        dp[s]=dp[s-1]+dp[s-2] 
        return
for i in range(n+1):
    step(i)
print(dp[-1]%1000000007)

Fixed submission:
n,m=map(int,input().split())
a=[]
mod=1000000007
for _ in range(m):
    a.append(int(input()))
a=set(a)
ans=[1]+[0]*(n)
for i in range(1,n+1):
    if i in a:
        ans[i]=0
    else:
        ans[i]=(ans[i-1]+ans[i-2])%mod
print(ans[n])
Buggy python submission (verdict: Time Limit Exceeded):
import sys


def input():
    return sys.stdin.readline().strip()


MOD = 998244353


def main():
    H, W = map(int, input().split())
    S = [input() for _ in range(H)]
    height = [[0] * W for _ in range(H)]
    width = [[0] * W for _ in range(H)]

    for h in range(H):
        cnt = 0
        for w in range(W):
            if S[h][w] == ".":
                cnt += 1
            else:
                width[h][w - cnt : w] = [cnt] * cnt
                cnt = 0
        width[h][W - cnt : W] = [cnt] * cnt
    for w in range(W):
        cnt = 0
        for h in range(H):
            if S[h][w] == ".":
                cnt += 1
            else:
                for i in range(cnt):
                    height[h - cnt + i][w] = cnt
                cnt = 0
        for i in range(cnt):
            height[H - cnt + i][w] = cnt
    answer = 0
    for h in range(H):
        for w in range(W):
            ans = width[h][w] + height[h][w] - 1
            if ans > answer:
                answer = ans
    print(answer)


if __name__ == "__main__":
    main()


Fixed submission:
import sys


def input():
    return sys.stdin.readline().strip()


MOD = 998244353


def main():
    H, W = map(int, input().split())
    S = [input() for _ in range(H)]
    height = [[0] * W for _ in range(H)]
    width = [[0] * W for _ in range(H)]

    for h in range(H):
        cnt = 0
        for w in range(W):
            if S[h][w] == ".":
                cnt += 1
            else:
                width[h][w - cnt : w] = [cnt] * cnt
                cnt = 0
        width[h][W - cnt : W] = [cnt] * cnt
    for w in range(W):
        cnt = 0
        for h in range(H):
            if S[h][w] == ".":
                cnt += 1
            else:
                for i in range(cnt):
                    height[h - cnt + i][w] = cnt
                cnt = 0
        for i in range(cnt):
            height[H - cnt + i][w] = cnt
    answer = 0
    for h in range(H):
        for w in range(W):
            ans = width[h][w] + height[h][w] - 1
            if ans > answer:
                answer = ans
    print(answer)


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
s=input()
s=s.replace('BC','D')
ans=0
while s.count('AD')>0:
    ans+=s.count('AD')
    s=s.replace('AD','DA')
print(ans)

Fixed submission:
import re
s=input()
ss=s.replace('BC','D')
sss=re.split('[BC]',ss)
ans=0
for i in sss:
    acnt=0
    for g in i:
        if g=='A':
            acnt+=1
        else:
            ans+=acnt
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
s=input()
ans=0
while s.count('AABCBC')>0:
    ans+=s.count('AABCBC')*4
    s=s.replace('AABCBC','BCBCAA')
while s.count('ABCBC')>0:
    ans+=s.count('ABCBC')*2
    s=s.replace('ABCBC','BCBCA')
while s.count('AABC')>0:
    ans+=s.count('AABC')*2
    s=s.replace('AABC','BCAA')
while s.count('ABC')>0:
    ans+=s.count('ABC')
    s=s.replace('ABC','BCA')
print(ans)

Fixed submission:
import re
s=input()
ss=s.replace('BC','D')
sss=re.split('[BC]',ss)
ans=0
for i in sss:
    acnt=0
    for g in i:
        if g=='A':
            acnt+=1
        else:
            ans+=acnt
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
s=input()
ans=0
while s.count('ABC')>0:
    ans+=s.count('ABC')
    s=s.replace('ABC','BCA')
print(ans)

Fixed submission:
import re
s=input()
ss=s.replace('BC','D')
sss=re.split('[BC]',ss)
ans=0
for i in sss:
    acnt=0
    for g in i:
        if g=='A':
            acnt+=1
        else:
            ans+=acnt
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n,m=map(int,input().split())
gate=[]
l,r=map(int,input().split())
for i in range(l,r+1):
    gate.append(i)
for i in range(m-1):
    l,r=map(int,input().split())
    g=[]
    for i in gate:
        if l<=i<=r:
            g.append(i)
    gate=g

print(len(gate))

Fixed submission:
n,m=map(int,input().split())
card=[]
L=1
R=n
for i in range(m):
    card.append([int(i) for i in input().split()])
for j in card:
    if j[0]<=R:
        if L<=j[0]:
            L=j[0]
            
    else:
        print(0)
        quit()
    if L<=j[1]:
        if j[1]<=R:
            R=j[1]
            
    else:
        print(0)
        quit()
print(R-L+1)

Buggy python submission (verdict: Time Limit Exceeded):
n,m=map(int,input().split())
gate=[0]*n
for i in range(m):
    l,r=map(int,input().split())
    for k in range(l-1,r):
        gate[k]+=1
print(gate.count(m))

Fixed submission:
n,m=map(int,input().split())
card=[]
L=1
R=n
for i in range(m):
    card.append([int(i) for i in input().split()])
for j in card:
    if j[0]<=R:
        if L<=j[0]:
            L=j[0]
            
    else:
        print(0)
        quit()
    if L<=j[1]:
        if j[1]<=R:
            R=j[1]
            
    else:
        print(0)
        quit()
print(R-L+1)

Buggy python submission (verdict: Time Limit Exceeded):
n,m=map(int,input().split())
gate=[]
for i in range(m):
    gate.append([int(i) for i in input().split()])
count=0
for k in range(1,n+1):
    g=0
    for j in gate:
        if j[0]<=k<=j[1]:
            g+=1
    if g==m:
        count+=1
print(count)


Fixed submission:
n,m=map(int,input().split())
card=[]
L=1
R=n
for i in range(m):
    card.append([int(i) for i in input().split()])
for j in card:
    if j[0]<=R:
        if L<=j[0]:
            L=j[0]
            
    else:
        print(0)
        quit()
    if L<=j[1]:
        if j[1]<=R:
            R=j[1]
            
    else:
        print(0)
        quit()
print(R-L+1)
Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
n,m=map(int,input().split())
a=sorted([int(i) for i in input().split()])
h=[]
for i in range(m):
    h.append([int(i) for i in input().split()])
h.sort(key=lambda x: x[1], reverse=True)
for j in h:
    k=np.sum(a[i]<j[1] for i in range(n))
    if k==0:
        break
    for g in range(min(k,j[0])):
        a[g]=j[1]
    a.sort()
print(sum(a))

Fixed submission:
n,m=map(int,input().split())
a=sorted([int(i) for i in input().split()])
bc=[list(map(int,input().split())) for _ in range(m)]
bc=sorted(bc,key=lambda x : x[1],reverse=True)
min_a=min(a)
count=0
for b,c in bc:
    if min_a >=c and count>=n:
        break
    else:
        l=min(b,n-count)
        for i in range(l):
            count+=1
            a.append(c)
a.sort()
print(sum(a[count:]))

Buggy python submission (verdict: Time Limit Exceeded):
n,m=map(int,input().split())
a=sorted([int(i) for i in input().split()])
h=[]
for i in range(m):
    h.append([int(i) for i in input().split()])
h.sort(key=lambda x: x[1], reverse=True)
for j in h:
    if a[0]<j[1]:
        for k in range(j[0]):
            if a[k]<j[1]:
                a[k]=j[1]
            else:
                break
        a.sort()
    else:
        break
print(sum(a))

Fixed submission:
n,m=map(int,input().split())
a=sorted([int(i) for i in input().split()])
bc=[list(map(int,input().split())) for _ in range(m)]
bc=sorted(bc,key=lambda x : x[1],reverse=True)
min_a=min(a)
count=0
for b,c in bc:
    if min_a >=c and count>=n:
        break
    else:
        l=min(b,n-count)
        for i in range(l):
            count+=1
            a.append(c)
a.sort()
print(sum(a[count:]))

Buggy python submission (verdict: Time Limit Exceeded):
n,m=map(int,input().split())
a=sorted([int(i) for i in input().split()])
h=[]
for i in range(m):
    h.append([int(i) for i in input().split()])
h.sort(key=lambda x: x[1], reverse=True)
for j in h:
    if a[0]<j[1]:
        for k in range(j[0]):
            d=max(a[k],j[1])
            a[k]=d
        a.sort()
    else:
        break
print(sum(a))

Fixed submission:
n,m=map(int,input().split())
a=sorted([int(i) for i in input().split()])
bc=[list(map(int,input().split())) for _ in range(m)]
bc=sorted(bc,key=lambda x : x[1],reverse=True)
min_a=min(a)
count=0
for b,c in bc:
    if min_a >=c and count>=n:
        break
    else:
        l=min(b,n-count)
        for i in range(l):
            count+=1
            a.append(c)
a.sort()
print(sum(a[count:]))

Buggy python submission (verdict: Time Limit Exceeded):
n,m=map(int,input().split())
a=sorted([int(i) for i in input().split()])
for i in range(m):
    b,c=map(int,input().split())
    for k in range(b):
        if a[k]<c:
            a[k]=c
    a.sort()
print(sum(a))


Fixed submission:
n,m=map(int,input().split())
a=sorted([int(i) for i in input().split()])
bc=[list(map(int,input().split())) for _ in range(m)]
bc=sorted(bc,key=lambda x : x[1],reverse=True)
min_a=min(a)
count=0
for b,c in bc:
    if min_a >=c and count>=n:
        break
    else:
        l=min(b,n-count)
        for i in range(l):
            count+=1
            a.append(c)
a.sort()
print(sum(a[count:]))
Buggy python submission (verdict: Time Limit Exceeded):
import sys


def input():
    return sys.stdin.readline().strip()


def dijkstra(s, n, w, cost):
    # 始点sから各頂点への最短距離
    # n:頂点数,　w:辺の数, cost[u][v] : 辺uvのコスト(存在しないときはinf)
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0

    while True:
        v = -1
        # まだ使われてない頂点の中から最小の距離のものを探す
        for i in range(n):
            if (not used[i]) and (v == -1):
                v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
            break
        used[v] = True
        for j in range(n):
            d[j] = min(d[j], d[v] + cost[v][j])
    return d


def main():
    N = int(input())
    cost = [[float("inf") for i in range(N)] for i in range(N)]

    for i in range(N - 1):
        u, v, w = map(int, input().split())
        cost[u - 1][v - 1] = w
        cost[v - 1][u - 1] = w
    D = dijkstra(0, N, N - 1, cost)
    for d in D:
        if d % 2 == 0:
            print(0)
        else:
            print(1)


if __name__ == "__main__":
    main()


Fixed submission:
import sys
import heapq


def input():
    return sys.stdin.readline().strip()


def dijkstra(start, n_nodes, edge):
    dist = [float("inf")] * n_nodes
    dist[start] = 0
    # 優先度キューの準備
    q = [(dist[start], start)]
    heapq.heapify(q)
    while q:
        # スタートから最も最短距離のものを取り出す
        d, i = heapq.heappop(q)
        # 記録してある情報よりも，取り出した要素に入っている距離情報の方が大きければ
        # 打ち切り．次の要素を取り出す操作に戻る
        if dist[i] < d:
            continue
        # そこから移動できる頂点を探し，最短距離が更新できるものがあれば，
        # 距離を更新して，その頂点への距離と頂点の方法を優先度キューにpush
        for cost, j in edge[i]:
            if dist[j] > dist[i] + cost:
                dist[j] = dist[i] + cost
                heapq.heappush(q, (dist[j], j))
    return dist


def main():
    N = int(input())
    edge = [[] for _ in range(N)]
    for i in range(N - 1):
        u, v, w = map(int, input().split())
        edge[u - 1].append([w, v - 1])
        edge[v - 1].append([w, u - 1])
    D = dijkstra(0, N, edge)
    for d in D:
        if d % 2 == 0:
            print(0)
        else:
            print(1)


if __name__ == "__main__":
    main()