結果
問題 | No.33 アメーバがたくさん |
ユーザー | siman |
提出日時 | 2022-04-15 02:01:33 |
言語 | Ruby (3.3.0) |
結果 |
AC
|
実行時間 | 83 ms / 5,000 ms |
コード長 | 1,144 bytes |
コンパイル時間 | 561 ms |
コンパイル使用メモリ | 11,196 KB |
実行使用メモリ | 15,292 KB |
最終ジャッジ日時 | 2023-08-26 00:50:53 |
合計ジャッジ時間 | 2,878 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 82 ms
15,012 KB |
testcase_01 | AC | 81 ms
15,292 KB |
testcase_02 | AC | 82 ms
15,064 KB |
testcase_03 | AC | 80 ms
15,000 KB |
testcase_04 | AC | 82 ms
15,280 KB |
testcase_05 | AC | 81 ms
15,152 KB |
testcase_06 | AC | 81 ms
15,108 KB |
testcase_07 | AC | 82 ms
15,112 KB |
testcase_08 | AC | 81 ms
15,116 KB |
testcase_09 | AC | 83 ms
15,244 KB |
testcase_10 | AC | 81 ms
15,252 KB |
コンパイルメッセージ
Syntax OK
ソースコード
class UnionFind def initialize(n) @size = Array.new(n, 1) @rank = Array.new(n, 0) @parent = [] (0..n).each do |i| @parent[i] = i end end def find(x) if @parent[x] == x x else @parent[x] = find(@parent[x]) end end def unite(x, y) x = find(x) y = find(y) return if x == y if @rank[x] < @rank[y] @parent[x] = y @size[y] += @size[x] else @parent[y] = x @size[x] += @size[y] @rank[x] += 1 if @rank[x] == @rank[y] end end def same?(x, y) find(x) == find(y) end def size(x) @size[find(x)] end end N, D, T = gets.split.map(&:to_i) X = gets.split.map(&:to_i).sort uf = UnionFind.new(N) 0.upto(N - 2) do |i| (i + 1).upto(N - 1) do |j| dist = (X[i] - X[j]).abs if dist % D == 0 && (X[j] - T * D) - (X[i] + T * D) <= D uf.unite(i, j) end end end pairs = Hash.new { |h, k| h[k] = [] } N.times do |i| pa = uf.find(i) pairs[pa] << i end ans = 0 pairs.each do |_, ids| min, max = ids.map { |id| X[id] }.minmax cnt = ((max + T * D) - (min - T * D)) / D + 1 ans += cnt end puts ans