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 |
|
|
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 |