Submission #1292461
Source Code Expand
require 'set' A, T, K = gets.split.map(&:to_i) areas, nums = [], Set.new A.times do nums << gets.to_i - 1 areas << gets.split.map{|s| s.to_i - 1}.to_set end M, cost, Es = gets.to_i, {}, Array.new(areas.size){Set.new} M.times do a, b, c = gets.split.map(&:to_i); a, b = a - 1, b - 1 cost[[a, b]], cost[[b, a]] = c, c areas.size.times do |ix| if areas[ix].member?(a) && areas[ix].member?(b) Es[ix] << [a, b] break end end end class UnionFind def initialize(n) @p = Array.new(n, -1) end def root(x) while @p[x] >= 0 x = @p[x] end x end def unite(x, y) x, y = self.root(x), self.root(y) if x != y x, y = y, x if @p[y] < @p[x] @p[x] += @p[y] @p[y] = x end end end def isST(edges) f = UnionFind.new(7) edges.each do |a, b| return false if f.root(a) == f.root(b) f.unite(a, b) end end spanlist = Hash.new{|h, k| h[k] = []} nums.sort.each do |num| [*0 .. num].combination(2).to_a.combination(num).each{|x| spanlist[num] << x if isST(x)} end costlist = [] (0 ... A).each do |ix| area = areas[ix] lkup = Hash[[*0 ... area.size].zip(area)] esum = Es[ix].inject(0){|s, e| s + cost[e]} acc = Hash.new(0) spanlist[area.size - 1].each do |x| plan = esum x.each do |a, b| v = cost[[lkup[a], lkup[b]]] break if v.nil? plan -= v end acc[plan] += 1 end costlist << acc.sort end dp = costlist[0] (1 ... costlist.size).each do |ix| acc = Hash.new(0) dp.product(costlist[ix]) do |(va, ca), (vb, cb)| v, c = va + vb, ca * cb acc[v] += c end acc = acc.sort dp, count = [], 0 acc.each do |v, c| count += c dp << [v, c] break if count >= K end end dp.sort! acc, ans = 0, -1 dp.each do |v, c| acc += c if acc >= K ans = v break end end puts ans
Submission Info
Submission Time | |
---|---|
Task | D - 覚醒ノ高橋君 |
User | noriakiokubo |
Language | Ruby (2.3.3) |
Score | 0 |
Code Size | 1928 Byte |
Status | WA |
Exec Time | 8408 ms |
Memory | 9880 KB |
Judge Result
Set Name | All | ||||||
---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 100 | ||||||
Status |
|
Set Name | Test Cases |
---|---|
All | 00_sample_01.txt, 00_sample_02.txt, 00_sample_03.txt, 01_randt_00.txt, 01_randt_01.txt, 01_randt_02.txt, 01_randt_03.txt, 01_randt_04.txt, 01_randt_05.txt, 01_randt_06.txt, 01_randt_07.txt, 01_randt_08.txt, 01_randt_09.txt, 01_randt_10.txt, 01_randt_11.txt, 01_randt_12.txt, 01_randt_13.txt, 01_randt_14.txt, 01_randt_15.txt, 01_randt_16.txt, 01_randt_17.txt, 01_randt_18.txt, 01_randt_19.txt, 01_randt_20.txt, 01_randt_21.txt, 01_randt_22.txt, 01_randt_23.txt, 01_randt_24.txt, 01_randt_25.txt, 01_randt_26.txt, 01_randt_27.txt, 01_randt_28.txt, 01_randt_29.txt, 02_maxrandt_00.txt, 02_maxrandt_01.txt, 02_maxrandt_02.txt, 02_maxrandt_03.txt, 02_maxrandt_04.txt, 02_maxrandt_05.txt, 02_maxrandt_06.txt, 02_maxrandt_07.txt, 02_maxrandt_08.txt, 02_maxrandt_09.txt, 02_maxrandt_10.txt, 02_maxrandt_11.txt, 02_maxrandt_12.txt, 02_maxrandt_13.txt, 02_maxrandt_14.txt, 02_maxrandt_15.txt, 02_maxrandt_16.txt, 02_maxrandt_17.txt, 02_maxrandt_18.txt, 02_maxrandt_19.txt, 03_overflow_00.txt, 03_overflow_01.txt, 03_overflow_02.txt, 03_overflow_03.txt, 03_overflow_04.txt, 03_overflow_05.txt, 03_overflow_06.txt, 03_overflow_07.txt, 03_overflow_08.txt, 03_overflow_09.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00_sample_01.txt | AC | 11 ms | 1916 KB |
00_sample_02.txt | AC | 10 ms | 1916 KB |
00_sample_03.txt | AC | 10 ms | 1916 KB |
01_randt_00.txt | AC | 840 ms | 6012 KB |
01_randt_01.txt | AC | 941 ms | 6012 KB |
01_randt_02.txt | WA | 749 ms | 6012 KB |
01_randt_03.txt | AC | 10 ms | 1916 KB |
01_randt_04.txt | WA | 443 ms | 6012 KB |
01_randt_05.txt | AC | 12 ms | 2044 KB |
01_randt_06.txt | WA | 313 ms | 6012 KB |
01_randt_07.txt | WA | 337 ms | 6012 KB |
01_randt_08.txt | AC | 352 ms | 6012 KB |
01_randt_09.txt | AC | 1569 ms | 6012 KB |
01_randt_10.txt | AC | 1930 ms | 6012 KB |
01_randt_11.txt | WA | 372 ms | 6012 KB |
01_randt_12.txt | AC | 37 ms | 2556 KB |
01_randt_13.txt | AC | 356 ms | 5756 KB |
01_randt_14.txt | AC | 354 ms | 6012 KB |
01_randt_15.txt | WA | 1119 ms | 6012 KB |
01_randt_16.txt | AC | 509 ms | 6012 KB |
01_randt_17.txt | WA | 329 ms | 5756 KB |
01_randt_18.txt | WA | 296 ms | 5628 KB |
01_randt_19.txt | WA | 495 ms | 6012 KB |
01_randt_20.txt | WA | 31 ms | 2556 KB |
01_randt_21.txt | WA | 326 ms | 5756 KB |
01_randt_22.txt | WA | 496 ms | 6012 KB |
01_randt_23.txt | AC | 10 ms | 1916 KB |
01_randt_24.txt | WA | 353 ms | 5756 KB |
01_randt_25.txt | WA | 366 ms | 6012 KB |
01_randt_26.txt | WA | 547 ms | 6012 KB |
01_randt_27.txt | AC | 1303 ms | 6012 KB |
01_randt_28.txt | AC | 696 ms | 6012 KB |
01_randt_29.txt | AC | 1768 ms | 6012 KB |
02_maxrandt_00.txt | AC | 4287 ms | 6136 KB |
02_maxrandt_01.txt | AC | 5096 ms | 8184 KB |
02_maxrandt_02.txt | AC | 7600 ms | 9848 KB |
02_maxrandt_03.txt | AC | 4903 ms | 7800 KB |
02_maxrandt_04.txt | WA | 3183 ms | 8080 KB |
02_maxrandt_05.txt | AC | 3412 ms | 6012 KB |
02_maxrandt_06.txt | AC | 3267 ms | 6012 KB |
02_maxrandt_07.txt | WA | 3183 ms | 8056 KB |
02_maxrandt_08.txt | AC | 5457 ms | 7800 KB |
02_maxrandt_09.txt | AC | 7192 ms | 8080 KB |
02_maxrandt_10.txt | AC | 5815 ms | 9880 KB |
02_maxrandt_11.txt | AC | 4561 ms | 7800 KB |
02_maxrandt_12.txt | AC | 6453 ms | 8696 KB |
02_maxrandt_13.txt | WA | 3444 ms | 6012 KB |
02_maxrandt_14.txt | AC | 3279 ms | 8056 KB |
02_maxrandt_15.txt | AC | 5379 ms | 7672 KB |
02_maxrandt_16.txt | AC | 4091 ms | 8056 KB |
02_maxrandt_17.txt | WA | 3384 ms | 6012 KB |
02_maxrandt_18.txt | AC | 7448 ms | 9848 KB |
02_maxrandt_19.txt | AC | 6180 ms | 7800 KB |
03_overflow_00.txt | AC | 3382 ms | 6012 KB |
03_overflow_01.txt | AC | 3181 ms | 6012 KB |
03_overflow_02.txt | AC | 4318 ms | 6012 KB |
03_overflow_03.txt | TLE | 8408 ms | 6140 KB |
03_overflow_04.txt | AC | 5867 ms | 6140 KB |
03_overflow_05.txt | AC | 3450 ms | 6012 KB |
03_overflow_06.txt | AC | 6085 ms | 6140 KB |
03_overflow_07.txt | AC | 5280 ms | 8060 KB |
03_overflow_08.txt | AC | 3167 ms | 6012 KB |
03_overflow_09.txt | AC | 3838 ms | 6012 KB |