Problem:


Score : 400 points

Problem Statement

We have a tree with N vertices numbered 1 to N.
The i-th edge in the tree connects Vertex u_i and Vertex v_i, and its length is w_i.
Your objective is to paint each vertex in the tree white or black (it is fine to paint all vertices the same color) so that the following condition is satisfied:

For any two vertices painted in the same color, the distance between them is an even number.

Find a coloring of the vertices that satisfies the condition and print it. It can be proved that at least one such coloring exists under the constraints of this problem.

Constraints

All values in input are integers.

1 \leq N \leq 10^5

1 \leq u_i < v_i \leq N

1 \leq w_i \leq 10^9

Input

Input is given from Standard Input in the following format:

N
u_1 v_1 w_1
u_2 v_2 w_2
.
.
.
u_{N - 1} v_{N - 1} w_{N - 1}

Output

Print a coloring of the vertices that satisfies the condition, in N lines.
The i-th line should contain 0 if Vertex i is painted white and 1 if it is painted black.

If there are multiple colorings that satisfy the condition, any of them will be accepted.

Sample Input 1

3
1 2 2
2 3 1

Sample Output 1

0
0
1

Sample Input 2

5
2 5 2
2 3 10
1 3 8
3 4 2

Sample Output 2

1
0
1
0
1



Sample input:
3
1 2 2
2 3 1


Sample output:
0
0
1

Submission status: Runtime Error

Solution code:
N = int(input())
edges = [[] for _ in range(N+1)]
for _ in range(N-1):
    u, v, w = map(int, input().split())
    edges[u].append([v, w])
    edges[v].append([u, w])
parent = [0 for _ in range(N)]
ans = [0 for _ in range(N)]


def dfs(edge, pd):
    for child, d in edges[edge]:
        if parent[child-1] == edge:
            continue
        cd = pd + d
        if cd % 2 == 0:
            ans[child-1] = 0
        else:
            ans[child-1] = 1
        parent[child-1] = edge
        dfs(child, cd)


def solve():
    dfs(1, 0)
    for i in range(N):
        print(ans[i])


if __name__ == '__main__':
    solve()

Submission status: Runtime Error

Solution code:
N = int(input())

tree = {}
for i in range(1,N):
    u, v, w = map(int, input().split())
    w = w%2
    if u in tree:
        tree[u].append([v,w])
    else:
        tree[u] = [[v,w]]

    if v in tree:
        tree[v].append([u,w])
    else:
        tree[v] = [[u,w]]

iro = [-1]*(N)
def seachTree(current, parent):
    if len(tree[current]) == 0:
        return

    for elms in tree[current]:
        if elms[0] == parent:
            continue
        if elms[1] == 0:
            iro[elms[0]-1] = iro[current-1]
        else:
            iro[elms[0]-1] = not iro[current-1]

        seachTree(elms[0], current)

iro[0] = False
seachTree(1, 0)
for val in iro:
    print(int(val))

Submission status: Runtime Error

Solution code:
N = int(input())

tree = {}
for i in range(1,N):
    u, v, w = map(int, input().split())
    w = w%2
    if u in tree:
        tree[u].append([v,w])
    else:
        tree[u] = [[v,w]]

    if v in tree:
        tree[v].append([u,w])
    else:
        tree[v] = [[u,w]]

iro = [-1]*(N)
def seachTree(current, parent):
    if len(tree[current]) == 0:
        return

    for elms in tree[current]:
        if elms[0] == parent:
            continue
        if elms[1] == 0:
            iro[elms[0]-1] = iro[current-1]
        else:
            iro[elms[0]-1] = not iro[current-1]

        seachTree(elms[0], current)

print(tree)
iro[0] = False
seachTree(1, 0)
for val in iro:
    print(int(val))

Submission status: Runtime Error

Solution code:
def dfs(v, c, total):
	if color[v] != -1:
		return
	color[v] = c
	for x in glaph[v]:
		u, w = x[0], x[1]
		total+=w
		if total%2 == 0:
			dfs(u, c, total)
		else:
			dfs(u, 1-c, total)
			
n = int(input())
glaph = [[]*n for _ in range(n)]
color = [-1]*n

for _ in range(n-1):
	u,v,w = map(int, input().split())
	glaph[u-1].append((v-1, w))
	glaph[v-1].append((u-1, w))	

dfs(v=0, c=0, total=0)
#for i in range(n):
#	print(i, glaph[i])
for i in color:
	print(i)

Submission status: Runtime Error

Solution code:
def dfs(v, c, total):
	if color[v] != -1:
		return
	color[v] = c
	for x in glaph[v]:
		u, w = x[0], x[1]
		total+=w
		if total%2 == 0:
			dfs(u, 0, total)
		else:
			dfs(u, 1, total)
			
n = int(input())
glaph = [[]*n for _ in range(n)]
color = [-1]*n

for _ in range(n-1):
	u,v,w = map(int, input().split())
	glaph[u-1].append((v-1, w))
	glaph[v-1].append((u-1, w))	

dfs(0, 0, 0)
for i in color:
	print(i)

Submission status: Runtime Error

Solution code:
# vをcに塗る。pはvの親
def dfs(v, p, c):
    res[v] = c
    for e in G[v]:
        if e[0] == p:
            continue
        if e[1] & 1:
            dfs(e[0], v, 1-c)
        else:
            dfs(e[0], v, c)


N = int(input())

G = [[] for _ in range(N)]
res = [0] * N
for _ in range(N-1):
    u, v, w = map(int, input().split())
    G[u-1].append([v-1, w])
    G[v-1].append([u-1, w])
dfs(0, -1, 1)
print('\n'.join(map(str, res)))

Submission status: Runtime Error

Solution code:
n=int(input())
tree=[[] for _ in range(n)]
for i in range(n-1):
    u,v,w = map(int,input().split())
    tree[u-1].append((v-1,w))
    tree[v-1].append((u-1,w))
    
color=[0]*(n+1)
q = [(-1,0,0)]
while q:
    parent,x,l = q.pop()
    for y in tree[x]:
        if y[0] == parent:
            continue
        q.append((x,*y))
    if l%2==1:
        color[x+1]=1
for i in range(1,n+1):
    print(color[i])

Submission status: Runtime Error

Solution code:
N = int(input())
tree = [[] for i in range(N)]
color = [-1] * N
for i in range(N-1):
  u, v, w = map(int, input().split())
  tree[u-1].append((v-1, w))
  tree[v-1].append((u-1, w))


def dfs(u):
  for v, w in tree[u]:
    if color[v] == -1:
      color[v] = color[u] ^ (w % 2)
      dfs(v)


color[0] = 0
dfs(0)
print('\n'.join(map(str, color)))

Submission status: Runtime Error

Solution code:
N = int(input())
tree = [[] for i in range(N)]
color = [-1] * N
for i in range(N-1):
    u, v, w = map(int, input().split())
    tree[u-1].append((v-1, w))
    tree[v-1].append((u-1, w))


def dfs(u):
    for v, w in tree[u]:
        if color[v] == -1:
            color[v] = color[u] ^ (w % 2)
            dfs(v)


color[0] = 0
dfs(0)
print('\n'.join(map(str, color)))

Submission status: Runtime Error

Solution code:
N = int(input())
edges = [list(map(int,input().split())) for _ in range(N-1)]
A = [[]for _ in range(N+1)]
ans = [-1]*(N+1)
for u,v,w in edges:
    A[u].append([v,w%2])
    A[v].append([u,w%2])

ans[1] = 0
def dfs(r):
    for a in A[r].copy():
        n = a[0]
        d = a[1]
        if ans[n] == -1:
            ans[n] = (ans[r] + d) % 2
            dfs(n)
dfs(1)
for a in ans[1:]:
    print(a%2)

Submission status: Runtime Error

Solution code:
N = int(input())
edges = [list(map(int,input().split())) for _ in range(N-1)]
A = [[]for _ in range(N+1)]
ans = [-1]*(N+1)
for u,v,w in edges:
    A[u].append([v,w])
    A[v].append([u,w])

ans[1] = 0
def dfs(r):
    for a in A[r].copy():
        n = a[0]
        d = a[1]
        if ans[n] == -1:
            ans[n] = (ans[r] + d) % 2
            dfs(n)
dfs(1)
for a in ans[1:]:
    print(a)

Submission status: Runtime Error

Solution code:
N = int(input())
edges = [list(map(int,input().split())) for _ in range(N-1)]
A = [[]for _ in range(N+1)]
ans = [-1]*(N+1)
for u,v,w in edges:
    A[u].append([v,w])
    A[v].append([u,w])

ans[1] = 0
def dfs(r):
    for a in A[r]:
        n = a[0]
        d = a[1]
        if ans[n] == -1:
            ans[n] = (ans[r] + d) % 2
            dfs(n)
dfs(1)
for a in ans[1:]:
    print(a)

Submission status: Runtime Error

Solution code:
N = int(input())
edges = [list(map(int,input().split())) for _ in range(N-1)]
A = [[]for _ in range(N+1)]
ans = [-1]*(N+1)
for u,v,w in edges:
    A[u].append([v,w])
    A[v].append([u,w])

ans[1] = 0
def dfs(r):
    for a in A[r]:
        n = a[0]
        d = a[1]
        if ans[n] == -1:
            ans[n] = ans[r] + d
            dfs(n)
dfs(1)
for a in ans[1:]:
    if a % 2 == 0:
        print(0)
    else:
        print(1)

Submission status: Runtime Error

Solution code:
import sys

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines


# rstrip().decode('utf-8')
# INF=float("inf")
#MOD=10**9+7
#sys.setrecursionlimit(2147483647)
# import math
import numpy as np
# import operator
#import bisect
#from heapq import heapify,heappop,heappush
#from math import gcd
# from fractions import gcd
#from collections import deque
#from collections import defaultdict
# from collections import Counter
#from itertools import accumulate
# from itertools import groupby
# from itertools import permutations
# from itertools import combinations
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import shortest_path
# from scipy.sparse.csgraph import csgraph_from_dense
from scipy.sparse.csgraph import dijkstra
# map(int,input().split())


def main():
	N=int(input())
	UVW = np.array(read().split(), np.int64)
	u=UVW[::3]
	v=UVW[1::3]
	w=UVW[2::3]
	U=np.append(u,v)
	V=np.append(v,u)
	W=np.append(w,w)
	
	
	graph1 = csr_matrix((W, (U, V)), (N + 1, N + 1))
	graph1_dist=shortest_path(graph1, indices=1)

	for i in range(1,N+1):
		print(int(graph1_dist[i]%2))




	
	
	
if __name__ == "__main__":
	main()

Submission status: Runtime Error

Solution code:
import sys

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines


# rstrip().decode('utf-8')
# INF=float("inf")
#MOD=10**9+7
#sys.setrecursionlimit(2147483647)
# import math
import numpy as np
# import operator
#import bisect
#from heapq import heapify,heappop,heappush
#from math import gcd
# from fractions import gcd
#from collections import deque
#from collections import defaultdict
# from collections import Counter
#from itertools import accumulate
# from itertools import groupby
# from itertools import permutations
# from itertools import combinations
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
# from scipy.sparse.csgraph import csgraph_from_dense
from scipy.sparse.csgraph import dijkstra
# map(int,input().split())


def main():
	N=int(input())
	UVW = np.array(read().split(), np.int64)
	u=UVW[::3]
	v=UVW[1::3]
	w=UVW[2::3]
	U=np.append(u,v)
	V=np.append(v,u)
	W=np.append(w,w)
	
	
	graph1 = csr_matrix((W, (U, V)), (N + 1, N + 1))
	graph1_dist=shortest_path(graph1, indices=1)

	for i in range(1,N+1):
		print(int(graph1_dist[i]%2))




	
	
	
if __name__ == "__main__":
	main()

Submission status: Runtime Error

Solution code:



N = int(input())
es = [[] for _ in range(N)]

for i in range(N-1):
    u,v,w = map(int, input().split())
    u,v = u-1, v-1
    es[u].append((v,w))
    es[v].append((u,w))


ans = [-1] * N

def dfs(node, c):

    ans[node] = c
    for next,w in es[node]:
        # 未着色であれば
        if ans[next] == -1:
            if w % 2 == 0:
                # 距離が偶数なら同じ色
                dfs(next, c)
            else:
                # 距離が異なるなら違う色
                if c == 0:
                    dfs(next, 1)
                else:
                    dfs(next, 0)

dfs(0,0)

print(*ans, sep="\n")

Submission status: Runtime Error

Solution code:



N = int(input())
es = [[] for _ in range(N)]

for i in range(N-1):
    u,v,w = map(int, input().split())
    u,v = u-1, v-1
    es[u].append((v,w))
    es[v].append((u,w))


ans = [-1] * N

def dfs(node, c):

    ans[node] = c
    for next,w in es[node]:
        # 未着色であれば
        if ans[next] == -1:
            if w % 2 == 0:
                # 距離が偶数なら同じ色
                dfs(next, c)
            else:
                # 距離が異なるなら違う色
                if c == 0:
                    dfs(next, 1)
                else:
                    dfs(next, 0)

dfs(0,0)

print(ans, sep="\n")

Submission status: Runtime Error

Solution code:
import sys

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines


# rstrip().decode('utf-8')
# INF=float("inf")
#MOD=10**9+7
#sys.setrecursionlimit(2147483647)
# import math
import numpy as np
# import operator
#import bisect
#from heapq import heapify,heappop,heappush
#from math import gcd
# from fractions import gcd
#from collections import deque
#from collections import defaultdict
# from collections import Counter
#from itertools import accumulate
# from itertools import groupby
# from itertools import permutations
# from itertools import combinations
from scipy.sparse import csr_matrix
# from scipy.sparse.csgraph import floyd_warshall
# from scipy.sparse.csgraph import csgraph_from_dense
from scipy.sparse.csgraph import dijkstra
# map(int,input().split())


def main():
	N=int(input())
	UVW = np.array(read().split(), np.int64)
	u=UVW[::3]
	v=UVW[1::3]
	w=UVW[2::3]
	U=np.append(u,v)
	V=np.append(v,u)
	W=np.append(w,w)
	
	
	graph1 = csr_matrix((W, (U, V)), (N + 1, N + 1))
	graph1_dist=dijkstra(graph1)
	
	ans=graph1_dist[1][1:]%2
	#print(graph1)
	for i in range(N):
		print(int(ans[i]))




	
	
	
if __name__ == "__main__":
	main()

Submission status: Runtime Error

Solution code:
import sys

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines


# rstrip().decode('utf-8')
# INF=float("inf")
#MOD=10**9+7
#sys.setrecursionlimit(2147483647)
# import math
import numpy as np
# import operator
#import bisect
#from heapq import heapify,heappop,heappush
#from math import gcd
# from fractions import gcd
#from collections import deque
#from collections import defaultdict
# from collections import Counter
#from itertools import accumulate
# from itertools import groupby
# from itertools import permutations
# from itertools import combinations
from scipy.sparse import csr_matrix
# from scipy.sparse.csgraph import floyd_warshall
# from scipy.sparse.csgraph import csgraph_from_dense
from scipy.sparse.csgraph import dijkstra
# map(int,input().split())


def main():
	N=int(input())
	UVW = np.array(read().split(), np.int64)
	u=UVW[::3]
	v=UVW[1::3]
	w=UVW[2::3]
	U=np.append(u,v)
	V=np.append(v,u)
	W=np.append(w,w)
	
	print(U,V)
	
	graph1 = csr_matrix((W, (U, V)), (N + 1, N + 1))
	graph1_dist=dijkstra(graph1)
	
	ans=graph1_dist[1][1:]%2
	print(graph1)
	for i in range(N):
		print(int(ans[i]))




	
	
	
if __name__ == "__main__":
	main()

Submission status: Runtime Error

Solution code:
import sys

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines


# rstrip().decode('utf-8')
# INF=float("inf")
#MOD=10**9+7
#sys.setrecursionlimit(2147483647)
# import math
import numpy as np
# import operator
#import bisect
#from heapq import heapify,heappop,heappush
#from math import gcd
# from fractions import gcd
#from collections import deque
#from collections import defaultdict
# from collections import Counter
#from itertools import accumulate
# from itertools import groupby
# from itertools import permutations
# from itertools import combinations
from scipy.sparse import csr_matrix
# from scipy.sparse.csgraph import floyd_warshall
# from scipy.sparse.csgraph import csgraph_from_dense
from scipy.sparse.csgraph import dijkstra
# map(int,input().split())


def main():
	N=int(input())
	UVW = np.array(read().split(), np.int64)
	U=UVW[::3]
	V=UVW[1::3]
	W=UVW[2::3]
	
	graph1 = csr_matrix((W, (U, V)), (N + 1, N + 1))
	graph1_dist=dijkstra(graph1,directed=False)
	
	ans=graph1_dist[1][1:]%2
	
	for i in range(N):
		print(int(ans[i]))




	
	
	
if __name__ == "__main__":
	main()

Submission status: Runtime Error

Solution code:
N = int(input())

B = [None]*N
for _ in range(N-1):
  u,v,w = input().split()
  u = int(u)-1
  v = int(v)-1
  w = int(w)
  
  if B[u] is None: B[u]=[]
  if B[v] is None: B[v]=[]
  B[u].append([v, w])
  B[v].append([u, w])
     
def calc_tree(i):
  #if B[i] is None: return
  for n,l in B[i]:
    paint_tree(n,l, ans[i])
  
def paint_tree(n, l, c):
  # if already painted, return
  if ans[n] is not None: return
  ans[n] = c if l%2==0 else not c
  calc_tree(n)

ans = [None]*N
ans[0] = False
if N>1:
  calc_tree(0)

for a in ans:
  if a is not None:
  	print(int(a))

Submission status: Runtime Error

Solution code:
N = int(input())

B = [None]*N
for _ in range(N-1):
  u,v,w = input().split()
  u = int(u)-1
  v = int(v)-1
  w = int(w)
  
  if B[u] is None: B[u]=[]
  if B[v] is None: B[v]=[]
  B[u].append([v, w])
  B[v].append([u, w])
     
def calc_tree(i):
  if B[i] is None: return
  for n,l in B[i]:
    paint_tree(n,l, ans[i])
  
def paint_tree(n, l, c):
  # if already painted, return
  if ans[n] is not None: return
  ans[n] = c if l%2==0 else not c
  calc_tree(n)

  
ans = [None]*N
ans[0] = False
calc_tree(0)

for a in ans:
  if a is not None:
  	print(int(a))

Submission status: Runtime Error

Solution code:
N = int(input())

B = [None]*(N)
for _ in range(N-1):
  #A = [int(i) for i in input().split()]
  u,v,w = input().split()
  u = int(u)-1
  v = int(v)-1
  w = int(w)
  
  if B[u] is None: B[u]=[]
  if B[v] is None: B[v]=[]
  B[u].append((v, w))
  B[v].append((u, w))
  

       
def calc_tree(i):
  if B[i] is None: return
  for n,l in B[i]:
    paint_tree(n,l, ans[i])
  
def paint_tree(n, l, c):
  if ans[n] is not None: return
  ans[n] = c if l%2==0 else not c
  calc_tree(n)

  
ans = [None]*N
ans[0] = False
calc_tree(0)

for a in ans:
  print(int(a))

Submission status: Runtime Error

Solution code:
N = int(input())

#A = []
B = [None]*(N)
for _ in range(N-1):
  A = [int(i) for i in input().split()]
  #A.append([int(i) for i in input().split()])
  if B[A[0]-1] is None: B[A[0]-1]=[]
  if B[A[1]-1] is None: B[A[1]-1]=[]
  B[A[0]-1].append((A[1]-1, A[2]))
  B[A[1]-1].append((A[0]-1, A[2]))
  
  #if B[A[0]-1] is None: B[A[0]-1]={}
  #if B[A[1]-1] is None: B[A[1]-1]={}
  #B[A[0]-1][A[1]-1]=A[2]
  #B[A[1]-1][A[0]-1]=A[2]

ans = [None]*(N)
def calc_tree(i):

  for n,l in B[i]:
    paint_tree(n,l, ans[i])
  
def paint_tree(n, l, c):
  if ans[n] is not None: return
  ans[n] = c if l%2==0 else not c
  if B[n] is not None:
    calc_tree(n)

ans[0] = False
calc_tree(0)

for a in ans:
  print(int(a))

Submission status: Runtime Error

Solution code:
N = int(input())
Tree = [[0]*N for i in range(N)]
for i in range(N-1):
    u,v,w = map(int,input().split())
    Tree[u-1][v-1] = Tree[v-1][u-1] = w

#print(Tree)
queue = [0]
Color=dict()
Color[0] = '0'
pre_num = list(range(1,N))

while queue:
    if len(Color) == N:
        break
    value = queue.pop(0)
    for i in pre_num:#range(N):
        if Tree[value][i] == 0: continue

        if Tree[value][i] % 2 == 0:
            queue.append(i)
            Color[i] = Color[value]
        else:
            queue.append(i)
            Color[i] = '1' if Color[value] == '0' else '0'
        pre_num.remove(i)
for i in range(N):
    print(Color[i])

Submission status: Runtime Error

Solution code:
n = int(input())
tree = [[] for i in range(n + 1)]
for i in range(n-1):
    u, v, w = map(int, input().split())
    tree[u].append([v,w])
    tree[v].append([u,w])
finished = set()
ans = [-1 for i in range(n + 1)]
def dfs(node, weight):
    finished.add(node)
    if weight % 2 == 0:
        ans[node] = 0
    else:
        ans[node] = 1
    for i in tree[node]:
        next, w = i
        if next not in finished:
            dfs(next, w + weight)
dfs(1,0)
for i in range(1, len(ans)):
    print(ans[i])

Submission status: Runtime Error

Solution code:
"""Even Relation
https://atcoder.jp/contests/abc126/tasks/abc126_d
"""
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10000)


class Node:
    def __init__(self, node_id, color):
        self.node_id = node_id
        self.color = color
        self.edges = []

class Edge:
    def __init__(self, to, length):
        self.to = to
        self.length = length


def dfs(node, p):
    for edge in node.edges:
        # 親への枝は何もしない
        if edge.to == p:
            continue
        # 枝が偶数なら子を同じ色で塗る
        if edge.length % 2 == 0:
            graph[edge.to].color = node.color
        else:
            if node.color == 1:
                graph[edge.to].color = 0
            else:
                graph[edge.to].color = 1

        dfs(graph[edge.to], node.node_id)


N = int(input())

# グラフ初期化
graph = [Node(node_id=i, color=-1) for i in range(N + 1)]
for i in range(N - 1):
    u, v, w = map(int, input().split())
    graph[u].edges.append(Edge(v, w))
    graph[v].edges.append(Edge(u, w))

# 最初は0始まり
graph[1].color = 0

dfs(graph[1], -1)


for i in range(1, N + 1):
    print(graph[i].color)

Submission status: Runtime Error

Solution code:
A, B, X = map(int, input().split())

def cost(N):
    return A * N + B * len(str(N))

if cost(10**9) < X:
    print(10**9)

else:

    left = 0
    right = 10**9
    while left < right - 1:
        mid = (right + left) // 2
        mid_cost = cost(mid)
        if mid_cost == X:
            break
        elif mid_cost > X:
            right = mid
        elif  mid_cost < X:
            left = mid

    print(left)

Submission status: Runtime Error

Solution code:
import heapq as hp
N = int(input())
ans = [-1]*N
arr = []
for i in range(N-1):
    u,v,w = map(int,input().split())
    u -= 1
    v -= 1
    arr.append([u,v,w])
e_list = [[] for i in range(N)]
for u,v,w in arr:
    e_list[u].add([v,w])
    e_list[v].add([u,w])

stack = [0]
ans[0] = 0
for rnd in range(N):
    if stack == []:
        break
    cur_pos = stack.pop()
    for des in e_list[cur_pos]:
        if ans[des] >  0:
            continue
        ans[des] = ans[cur_pos] + e_list[des][cur_pos]
        stack.append(des)
for i in ans:
    print(i)

Submission status: Runtime Error

Solution code:
n=int(input())
A=[]
ans=[-1]*n
for i in range(n):
  a,b,c=map(int,input().split())
  A.append([a,b,c])
ans[0]==0
A=sorted(A)
for i in range(1,n):
  for j in range(n):
    if A[j][0]== i:
      if A[j][2]%2==0:
        ans[A[j][1]]==0
      else:
        ans[A[j][1]]==1
    elif A[j][1]==i:
      if A[j][2]%2==0:
        ans[A[j][1]]==0
      else:
        ans[A[j][1]]==1

Submission status: Runtime Error

Solution code:
n=int(input())
dis=[10**15]*n
dis[0]=0
pair=[[]for _ in range(n)]
for i in range(n-1):
	a,b,c=map(int,input().split())
	pair[a-1].append([b-1,c])
	pair[b-1].append([a-1,c])
now=0
stack=set()
cnt=n-1
while cnt!=0:
	for i in range(len(pair[now])):
		if dis[pair[now][i][0]]==10**15:
			dis[pair[now][i][0]]=dis[now]+pair[now][i][1]
			stack.add(pair[now][i][0])
			new_now=pair[now][i][0]
	now=new_now
	stack.remove(now)
	cnt-=1
for i in range(n):
	if dis[i]%2==0:
		print(0)
	else:
		print(1)

Submission status: Runtime Error

Solution code:
def p_d():
    from sys import stdin

    input = stdin.readline
    n = int(input())
    route = [[] for _ in range(n)]
    for _ in range(n - 1):
        u, v, w = map(int, input().split())
        w = 0 if w & 1 == 0 else 1
        route[u - 1].append((v - 1, w))
        route[v - 1].append((u - 1, w))

    ans = [-1] * n

    def dfs(p, d):
        ans[p] = d
        for i, j in route[p]:
            if ans[i] < 0:
                dfs(i, d ^ j)

    dfs(0, 0)
    print("\n".join(map(str, ans)))
    
p_d()

Submission status: Runtime Error

Solution code:
def p_d():
    from sys import stdin

    input = stdin.readline
    n = int(input())
    route = [[] for _ in range(n)]
    for _ in range(n - 1):
        u, v, w = map(int, input().split())
        w = 0 if w & 1 == 0 else 1
        route[u - 1].append((v - 1, w))
        route[v - 1].append((u - 1, w))

    ans = [-1] * n

    def dfs(p, d):
        ans[p] = d
        for i, j in route[p]:
            if ans[i] < 0:
                dfs(i, d & j)

    dfs(0, 0)
    print("\n".join(map(str, ans)))
    
p_d()

Submission status: Runtime Error

Solution code:
N = int(input())
graph = [[] for _ in range(N+1)]
for _ in range(N-1):
    u,v,w = map(int,input().split(' '))
    graph[u].append((v,w))
    graph[v].append((u,w))

color_list = [-1]*(N+1)
color_list[1] = 0
'''
for i in range(1,N+1):
    for node in graph[i]:
        if node[1]%2 ==0:
            num =  color_list[i]
        else:
            num =  0 if color_list[i] == 1 else 1
        if color_list[node[0]] == -1:
            color_list[node[0]] = num
'''
def search(n):
    for node in graph[n]:
        if node[1]%2 ==0:
            num =  color_list[n]
        else:
            num =  0 if color_list[n] == 1 else 1
        if color_list[node[0]] == -1:
            color_list[node[0]] = num
            search(node[0]) 
search(1)
print(color_list)
for i in range(1,N+1):
    print(color_list[i])

Submission status: Runtime Error

Solution code:
from collections import defaultdict

G = defaultdict(list)

N = int(input())
C = [0 for i in range(N)]
last = N


def rec(pos, c):
    """ 2 色で塗ることができることが保証されている """
    global C
    C[pos] = c
    for to in G[pos]:
        if C[to] == 0:
            rec(to, -c)


for i in range(N-1):
    u, v, w = map(int, input().split())
    u -= 1; v -= 1
    # 無向グラフ
    if w%2 == 0:
        G[u].append(last)
        G[last].append(u)
        G[v].append(last)
        G[last].append(v)
        C.append(0)
        last += 1
    else:
        G[u].append(v)
        G[v].append(u)
rec(0, 1)
for i in range(N):
    print(0 if C[i] == -1 else 1)

Submission status: Runtime Error

Solution code:
"""
dfs活用問題
- 2部グラフ作成
- https://atcoder.jp/contests/abc126/tasks/abc126_d
"""
from collections import deque

n = int(input())
graph = [[] for _ in range(n)]
for _ in range(n-1):
    (u, v, w) = map(int, input().split())
    graph[u-1].append([v-1, w])
    graph[v-1].append([u-1, w])


def dfs_recursive(n, graph):
    def dfs(graph, colors, cur, depth):
        colors[cur] = depth % 2
        for child in graph[cur]:
            child_index = child[0]
            if -1 != colors[child_index]:
                continue
            dfs(graph, colors, child_index, depth + child[1])
    colors = [-1 for _ in range(n)]
    dfs(graph, colors, 0, 0)
    for i in colors:
        print(i)


def dfs_with_queue(n, grpah):
    q = deque()
    ans = [-1 for _ in range(n)]
    q.append(0)
    ans[0] = 0
    while 0 != len(q):
        v = q.popleft()
        for neigbhor in graph[v]:
            u = neigbhor[0]
            w = neigbhor[1]
            if -1 != ans[u]:
                continue
            ans[u] = (ans[v] + w) % 2
            q.append(u)
        for i in ans:
            print(i)


dfs_recursive(n, graph)

Submission status: Runtime Error

Solution code:
# ABC126 D - Even Relation
# import sys
# sys.setrecursionlimit(20000000)

def dfs(node,distance):
    for next_node,edge_distangce in G[node]:
        if ans[next_node]==-1:
            ans[next_node] = (distance+edge_distangce)%2
            dfs(next_node,distance+edge_distangce)

N = int(input())
G = [[] for _ in range(N)]

for i in range(N-1):
    u,v,w = map(int,input().split())
    G[u-1].append([v-1,w])
    G[v-1].append([u-1,w])

ans = [-1]*N
dfs(0,0)
print(*ans,sep='\n')

Submission status: Runtime Error

Solution code:
from heapq import heappop, heappush, heapify


def heapq_dijkstra(cost, num_v, start):
    """
    ダイクストラ法
    :param cost: 隣接行列
    :param num_v: 頂点数
    :param start: 始点
    :return:
    """
    inf = 10**5
    dist = [(inf if i != start - 1 else 0, i) for i in range(num_v)]
    heapify(dist)
    result = [inf] * num_v
    while dist:
        c, v = heappop(dist)
        next_dist = []
        for f_c, i in dist:
            f_c = min(f_c, c + cost[v][i])
            heappush(next_dist, (f_c, i))
        result[v] = c
        dist = next_dist

    return result


def dijkstra(cost, num_v, start):
    """
    ダイクストラ法
    :param cost: 隣接行列
    :param num_v: 頂点数
    :param start: 始点
    :return:
    """
    inf = float("inf")
    dist = [inf] * num_v
    used = [False] * num_v
    dist[start - 1] = 0
    while True:
        v = -1
        for i in range(num_v):
            if (not used[i]) and (v == -1):
                v = i
            elif (not used[i]) and (dist[i] < dist[v]):
                v = i
        if v == -1:
            break
        used[v] = True

        for i in range(num_v):
            dist[i] = min(dist[i], dist[v] + cost[v][i])
    return dist


def abc035_d():
    n, m, t = map(int, input().split())
    *a, = map(int, input().split())
    inf = float("inf")
    go_cost = [[inf] * n for _ in range(n)]
    re_cost = [[inf] * n for _ in range(n)]
    for _ in range(m):
        f_, t_, c = map(int, input().split())
        go_cost[f_ - 1][t_ - 1] = c
        re_cost[t_ - 1][f_ - 1] = c

    go_route = heapq_dijkstra(go_cost, n, 1)
    re_route = heapq_dijkstra(re_cost, n, 1)
    ans = [_a * (t - go_route[i] - re_route[i]) for i, _a in enumerate(a)]
    print(max(ans))


if __name__ == '__main__':
    abc035_d()

Submission status: Runtime Error

Solution code:
def dfs(node, distance):
    for next_node, edge_size in G[node]:
        if ans[next_node] == -1:
            ans[next_node] = ((distance + edge_size) % 2)
            dfs(next_node, distance + edge_size)

N = int(input())

G = [[] for i in range(N)]
for i in range(N - 1):
    u, v, w = map(int, input().split())
    G[u - 1].append([v - 1, w])
    G[v - 1].append([u - 1, w])

ans = [-1] * N
dfs(0, 0)
print(*ans, sep='\n')

Submission status: Runtime Error

Solution code:
N = int(input())
G = [[] for i in range(N)]

for i in range(N):
    u,v,w = map(int,input().split())
    w = w%2
    G[u].append((v,w))
    G[v].append((u,w))
ans = [ -1 for i in range(N)]
ans[0] = 0
stack = [1]

while len(stack) > 0:
    x = stack.pop()
    p = ans[x-1]
    g = len(G[x])
    for i in range(g):
        y = G[x][i][0]
        z = G[x][i][1]
        a = ans[y-1]
        if a == -1:
            stack.append(y)
            if z == 0:
                ans[y-1] = p
            else:
                ans[y-1] = 1-p
for i in range(N):
    print(ans[i])

Submission status: Runtime Error

Solution code:
n = int(input())

path = [[] for i in range(n)]

for _ in range(n-1):
    u,v,w = list(map(int,input().split()))
    path[u-1].append((v-1, w%2))
    path[v-1].append((u-1, w%2))

global dist
dist = [-1 for i in range(n)]
dist[0] = 0

def dfs(now):
    for v,w in path[now]:
        if dist[v] == -1:
            dist[v] = w + dist[now]
            dfs(v)
    
dfs(0)

for i in dist:
    print(i%2)

Submission status: Runtime Error

Solution code:
n = int(input())

path = [[] for i in range(n)]

for _ in range(n-1):
    u,v,w = list(map(int,input().split()))
    path[u-1].append((v-1, w))
    path[v-1].append((u-1, w))

global dist
dist = [-1 for i in range(n)]
dist[0] = 0

def dfs(now):
    for v,w in path[now]:
        if dist[v] == -1:
            dist[v] = w + dist[now]
            dfs(v)
    
dfs(0)

for i in dist:
    print(i%2)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**10)

class Node:
    def __init__(self):
        self.val = None
        self.a = []

n = int(input())
nodes = []

for i in range(n):
    nodes.append(Node())

for i in range(n-1):
    u, v, w = map(int, input().split())
    node1 = nodes[u-1]
    node2 = nodes[v-1]
    node1.a.append([node2, w])
    node2.a.append([node1, w])

root = nodes[0]
root.val = True
nodeSet = set()

def traverse(node):
    if node in nodeSet:
        return
    else:
        nodeSet.add(node)

    for pair in node.a:
        adjNode = pair[0]
        dis = pair[1]
        if dis % 2 == 0:
            adjNode.val = node.val
        else:
            adjNode.val = not node.val
        traverse(adjNode)

traverse(root)

for i in range(n):
    node = nodes[i]
    if node.val:
        print(1)
    else:
        print(0)