Submission #53204970

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),*ABC = $<.map{|ln| ln.split.map(&:to_i) }
G = (N+1).times.map{|i| [[i,0]] }
F = lambda{|a|
  G[a].kind_of?(Array) ? a : G[a] = F[G[a]]
}
U = lambda{|(a,b,c)| # a が c だけ b より後ろ
  ra,rb = F[a],F[b]
  next if ra==rb
  da = G[ra].find{|i,d| i==a }[1]
  db = G[rb].find{|i,d| i==b }[1]
  # db+c <=> da
  if db+c<da # G[rb] をずらして G[ra] に併合する。G[ra] の先頭の方が前にある。
    dd = da-(db+c)
    G[ra].concat G[rb].map{|i,d|
      [i,d+dd]
    }
    G[rb] = ra
  else # G[ra] をずらして G[rb] に併合する。G[rb] の先頭の方が前にある。
    dd = db+c-da
    G[rb].concat G[ra].map{|i,d|
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

(N,M),*ABC = $<.map{|ln| ln.split.map(&:to_i) }

G = (N+1).times.map{|i| [[i,0]] }
F = lambda{|a|
	G[a].kind_of?(Array) ? a : G[a] = F[G[a]]
}
U = lambda{|(a,b,c)| # a が c だけ b より後ろ
	ra,rb = F[a],F[b]
	next if ra==rb
	da = G[ra].find{|i,d| i==a }[1]
	db = G[rb].find{|i,d| i==b }[1]
	# db+c <=> da
	if db+c<da # G[rb] をずらして G[ra] に併合する。G[ra] の先頭の方が前にある。
		dd = da-(db+c)
		G[ra].concat G[rb].map{|i,d|
			[i,d+dd]
		}
		G[rb] = ra
	else # G[ra] をずらして G[rb] に併合する。G[rb] の先頭の方が前にある。
		dd = db+c-da
		G[rb].concat G[ra].map{|i,d|
			[i,d+dd]
		}
		G[ra] = rb
	end
}
ABC.each(&U)

G.shift
G.select!{|g| g.kind_of? Array }
G.map!{|g|
	[g,
	 g.inject(0){|m,(i,d)| m|1<<d },
	 [nil]*N
	]
}
G.sort_by!{_2}
H = G.inject(lambda{|_| true }){|nx,(g,m,ss)|
	sx = N-m.bit_length
	next Hash.new{|h,z|
		h[z] = ! (0..sx).select{|s|
			z&m<<s==0 && nx[z|m<<s]
		}.each{|s|
			ss[s] = s
		}.empty?
	}
}
H[0]

Ans = [-1]*(N+1)
G.each{|g,_,ss|
	s,ex = ss.compact
	g.each{|i,d|
		Ans[i] = s+1+d
	} if s && ! ex
}
puts Ans[1,N]*' '

Submission Info

Judge Result