Submission #63566575

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
(N,M),*XYZ = $<.map{|ln| ln.split.map(&:to_i) }
G = [-1]*(N+1)
F = lambda{|a|
  G[a]<0 ? a : G[a] = F[G[a]]
}
U = lambda{|a,b|
  a,b = F[a],F[b]
  next if a==b
  a,b = b,a if G[b]<G[a]
  G[a] += G[b]
  G[b] = a
}
E = Array.new(N+1){[]}
XYZ.each{|x,y,z|
  U[x,y]
  E[x]<<[y,z]
  E[y]<<[x,z]
}
A = [nil]*(N+1)
(1..N).group_by(&F).each{|r,gs|
  A[r] = 0
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

(N,M),*XYZ = $<.map{|ln| ln.split.map(&:to_i) }
G = [-1]*(N+1)
F = lambda{|a|
	G[a]<0 ? a : G[a] = F[G[a]]
}
U = lambda{|a,b|
	a,b = F[a],F[b]
	next if a==b
	a,b = b,a if G[b]<G[a]
	G[a] += G[b]
	G[b] = a
}
E = Array.new(N+1){[]}
XYZ.each{|x,y,z|
	U[x,y]
	E[x]<<[y,z]
	E[y]<<[x,z]
}
A = [nil]*(N+1)
(1..N).group_by(&F).each{|r,gs|
	A[r] = 0
	q = [r]
	while (x = q.shift)
		a = A[x]
		E[x].each{|y,z|
			z ^= a
			if A[y]
				if A[y]!=z
					p(-1)
					exit
				end
			else
				A[y] = z
				q<<y
			end
		}
	end
	a0 = (30.times.map{|b|
		n = gs.sum{|i| A[i][b] }
		m = gs.size-n
		next [n<m ? 0 : 1]
	}.reverse*'').to_i(2)
	gs.each{|i|
		A[i] ^= a0
	}
}
puts A[1,N].map{_1||0}*' '

Submission Info

Judge Result