Submission #27932085

---

Source Code Expand

$ln = $<.map{|ln| ln.split.map(&:to_i) }
N,M,K = $ln.shift
UV = $ln.shift M
S = 0,*$ln.shift
Q, = $ln.shift
AB = $ln.shift Q

ST2UV = Hash.new{|h,st| h[st] = [] }
G = [-1]*(N+1)
F = lambda{|u|
	G[u]<0 ? u : G[u] = F[G[u]]
}
U = lambda{|u,v|
	u,v = F[u],F[v]
	next if u==v
	u,v = v,u if G[v]<G[u]
	G[u] += G[v]
	G[v] = u
}
UV.each{|u,v|
	s,t = S[u],S[v]
	if s==t
		U[u,v]
	else
		ST2UV[s+t+[s,t].max*K]<<u<<v
	end
}

Ans = [nil]*Q
Q.times.group_by{|q|
	AB[q].map{|a| S[a] }.then{|st| st.sum+st.max*K }
}.each{|st,qs|
	f2 = Hash.new{|h,f|f}
	ST2UV[st].each{|u| f2[F[u]] = 0 }
	qs.each{|q|
		a,b = AB[q].map{|a| f2[F[a]] }
		Ans[q] = a==b ? 1 : 0
	}
}

puts Ans

Submission Info

Judge Result