Submission #2872317

---

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]
    uf.unite(i, i+1) if white[i+1] && i%7<6
    uf.unite(i, i+7) if white[i+7] && i+7<m 
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

Judge Result