Submission #2388005


Source Code Expand

require 'pp'
# IS_DEBUG = true
IS_DEBUG = false
def dputs str
	if(IS_DEBUG)
		puts str
	end
end
def dpp str
	if(IS_DEBUG)
		pp str
	end
end

require 'pp'

def one2zero(g)
	g.map{|v1,v2,w| [v1-1,v2-1,w]}
end

w_i = 2

class Unionfind
	class Set
		attr_accessor :self, :parent, :rank
		def initialize(x)
			@self = x
			@parent = x
			@rank = 0
		end
	end
	def initialize(num)
		@sets = Array.new(num){|i| makeset(i)}
	end
	def makeset(i)
		Set.new(i)
	end
	# return tree number x.self
	def find(x)
		sx = @sets[x]
		if(sx.parent == x)
			return x
		else
			sx.parent = find(sx.parent)
			return sx.parent
		end
	end
	def union(x,y)
		xr = find(x)
		yr = find(y)
		if(@sets[xr].rank > @sets[yr].rank)
			@sets[yr].parent = xr
		elsif(@sets[xr].rank < @sets[yr].rank)
			@sets[xr].parent = yr
		elsif(xr != yr)
			@sets[yr].parent = xr
			@sets[xr].rank += 1
		end
	end
end

# answer the weight of min spanning tree of g containing e
# g is all edges of the graph, representating the graph
def kraskal(g_sorted, num_vertexes, e=[])
	def connect(v1,v2,v2t)
		# t2 merge to t1
		r1 = v2t.find(v1)
		r2 = v2t.find(v2)
		v2t.union(r1,r2)
	end
	
	# init
	# generate forest mapping vertex i to tree i
	# 0 indexed : vertex i+1 (1 indexed) and tree i+1 map to vartex[i]=i
	v2t = Unionfind.new(num_vertexes)
	num_rest = num_vertexes - 1
	w_tree = 0
	
	# optinal behavior
	# fixed edge to select
	e.each{|v1,v2,w|
		num_rest -= 1
		w_tree += w
		connect(v1,v2,v2t)
	}

	# start
	g_sorted.each{|v1,v2,w|
		if(num_rest == 0)
			break
		end
		dputs "compare tree of #{v1} #{v2} #{w} : #{v2t.find(v1)} #{v2t.find(v2)}"
		if(v2t.find(v1)!=v2t.find(v2))
			connect(v1,v2,v2t)
			num_rest -= 1
			w_tree += w
		end
	}
	return w_tree
end

def mod_pow(a,n)
	mod = 1000000007
	if(n==1)
		return a
	end
	m = n/2
	mpa = mod_pow(a,m)
	mpa2 = (mpa * mpa) % mod
	if(n%2 != 0)
		 mpa2 = (mpa2 * a) % mod
	end
	mpa2
end
def f(x,d_min,num_edge)
	num = d_min.inject(0){|sum,n| n <= x ? sum+1 : sum}
	dputs "num is #{num}"
	if(num == 0)
		mod_pow(2, num_edge)
	else
		mod_pow(2,num_edge-num+1)
	end
end

N,M=gets.chomp.split(' ').map{|n| n.to_i}
X,d=gets.chomp.split(' ').map{|n| n.to_i}
g = Array.new(M)
0.upto(M-1){|d|
	g[d]=gets.chomp.split(' ').map{|n| n.to_i}
}
g = one2zero(g)
g = g.sort{|e1,e2| e1[w_i] <=> e2[w_i]}

d_min = Array.new(M)
g.each_with_index{|e,i|
	d_min[i] = kraskal(g,N,[e])
}
dputs "dmin is "
dpp d_min

puts "#{f(X-1,d_min,M) - f(X,d_min,M)}"

Submission Info

Submission Time
Task E - Bichrome Spanning Tree
User kou65536
Language Ruby (2.3.3)
Score 0
Code Size 2577 Byte
Status WA
Exec Time 2107 ms
Memory 4600 KB

Compile Error

./Main.rb:128: warning: shadowing outer local variable - d
./Main.rb:126: warning: assigned but unused variable - d

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 900
Status
AC × 4
AC × 6
WA × 1
TLE × 45
Set Name Test Cases
Sample sample-01.txt, sample-02.txt, sample-03.txt, sample-04.txt
All 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, 37.txt, 38.txt, 39.txt, 40.txt, 41.txt, 42.txt, 43.txt, 44.txt, 45.txt, 46.txt, 47.txt, 48.txt, sample-01.txt, sample-02.txt, sample-03.txt, sample-04.txt
Case Name Status Exec Time Memory
01.txt TLE 2107 ms 2428 KB
02.txt TLE 2107 ms 2428 KB
03.txt TLE 2107 ms 2428 KB
04.txt TLE 2107 ms 2428 KB
05.txt TLE 2107 ms 2428 KB
06.txt TLE 2107 ms 2428 KB
07.txt TLE 2107 ms 2428 KB
08.txt TLE 2107 ms 2428 KB
09.txt TLE 2107 ms 2428 KB
10.txt TLE 2107 ms 2428 KB
11.txt TLE 2107 ms 2428 KB
12.txt TLE 2107 ms 2424 KB
13.txt TLE 2107 ms 2424 KB
14.txt TLE 2107 ms 2424 KB
15.txt TLE 2107 ms 2428 KB
16.txt TLE 2107 ms 2428 KB
17.txt TLE 2107 ms 2428 KB
18.txt TLE 2107 ms 4472 KB
19.txt TLE 2107 ms 2428 KB
20.txt TLE 2107 ms 2428 KB
21.txt TLE 2107 ms 2428 KB
22.txt TLE 2107 ms 2428 KB
23.txt TLE 2107 ms 2428 KB
24.txt TLE 2107 ms 2424 KB
25.txt TLE 2107 ms 4600 KB
26.txt TLE 2107 ms 2428 KB
27.txt TLE 2107 ms 2428 KB
28.txt TLE 2107 ms 2428 KB
29.txt TLE 2107 ms 4476 KB
30.txt TLE 2107 ms 2428 KB
31.txt TLE 2107 ms 2428 KB
32.txt TLE 2107 ms 2428 KB
33.txt TLE 2107 ms 2428 KB
34.txt TLE 2107 ms 2428 KB
35.txt WA 720 ms 2428 KB
36.txt AC 795 ms 2428 KB
37.txt AC 989 ms 2428 KB
38.txt TLE 2107 ms 2428 KB
39.txt TLE 2107 ms 2428 KB
40.txt TLE 2107 ms 2428 KB
41.txt TLE 2107 ms 2428 KB
42.txt TLE 2107 ms 2428 KB
43.txt TLE 2107 ms 2424 KB
44.txt TLE 2107 ms 2424 KB
45.txt TLE 2107 ms 2424 KB
46.txt TLE 2107 ms 2428 KB
47.txt TLE 2107 ms 2424 KB
48.txt TLE 2107 ms 2424 KB
sample-01.txt AC 11 ms 2044 KB
sample-02.txt AC 11 ms 2044 KB
sample-03.txt AC 11 ms 2044 KB
sample-04.txt AC 12 ms 2044 KB