Submission #2872261
Source Code Expand
class UnionFind attr_reader :set_size def initialize(n) @par = Array.new(n) n.times{ |i| @par[i] = i } @rank = Array.new(n, 0) @set_size = Array.new(n, 0) end def find(x) if @par[x] == x x else @par[x] = find(@par[x]) end end def unite(x,y) x = find(x) y = find(y) return if x == y if @rank[x] < @rank[y] @par[x] = y @set_size[y] += @set_size[x] else @par[y] = x @set_size[x] += @set_size[y] @rank[x] += 1 if @rank[x] == @rank[y] end end def same?(x, y) find(x) == find(y) end end n, m, q = gets.split.map(&:to_i) as = gets.split.map(&:to_i) if m % 7 != 0 (1..6).each do |i| as.concat(as[0, q].map{|a| a+i*m}) end m *= 7 q *= 7 end uf = UnionFind.new(m) white = Array.new(m, true) as.each{|a| white[a] = false} m.times do |i| next unless white[i] [i-1, i+1, i-7, i+7].each do |j| if white[j] && j.between?(0, m-1) uf.unite(i, j) end end end blocks = 7*n/m num = m.times.count{|i| white[i] && uf.find(i) == i} * blocks used = {} 7.times do |i| j = m-7+i if white[i] && white[j] && !(used[uf.find(i)] && used[uf.find(j)]) num -= blocks - 1 used[uf.find(i)] = true used[uf.find(j)] = true end end puts num
Submission Info
Submission Time | |
---|---|
Task | C - Calendar 2 |
User | betrue12 |
Language | Ruby (2.3.3) |
Score | 90 |
Code Size | 1515 Byte |
Status | WA |
Exec Time | 1060 ms |
Memory | 26960 KB |
Judge Result
Set Name | Sample | Subtask1 | Subtask2 | Subtask3 | Subtask4 | ||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 100 | 90 / 90 | 0 / 200 | 0 / 110 | ||||||||||||||||||||
Status |
|
|
|
|
|
Set Name | Test Cases |
---|---|
Sample | sub0_in1.txt, sub0_in2.txt |
Subtask1 | sub0_in1.txt, sub0_in2.txt, sub1_in1.txt, sub1_in2.txt, sub1_in3.txt, sub1_in4.txt, sub1_in5.txt |
Subtask2 | sub2_in1.txt |
Subtask3 | sub2_in1.txt, sub3_in1.txt, sub3_in2.txt |
Subtask4 | sub0_in1.txt, sub0_in2.txt, sub1_in1.txt, sub1_in2.txt, sub1_in3.txt, sub1_in4.txt, sub1_in5.txt, sub2_in1.txt, sub3_in1.txt, sub3_in2.txt, sub4_in1.txt, sub4_in2.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
sub0_in1.txt | AC | 7 ms | 1788 KB |
sub0_in2.txt | AC | 7 ms | 1788 KB |
sub1_in1.txt | AC | 7 ms | 1788 KB |
sub1_in2.txt | AC | 7 ms | 1788 KB |
sub1_in3.txt | AC | 7 ms | 1788 KB |
sub1_in4.txt | WA | 7 ms | 1788 KB |
sub1_in5.txt | TLE | 1060 ms | 26064 KB |
sub2_in1.txt | AC | 61 ms | 10004 KB |
sub3_in1.txt | WA | 208 ms | 7804 KB |
sub3_in2.txt | WA | 211 ms | 4860 KB |
sub4_in1.txt | TLE | 1060 ms | 26960 KB |
sub4_in2.txt | TLE | 1060 ms | 16892 KB |