結果
問題 |
No.1147 土偶Ⅱ
|
ユーザー |
|
提出日時 | 2021-11-02 20:24:15 |
言語 | Ruby (3.4.1) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,035 bytes |
コンパイル時間 | 70 ms |
コンパイル使用メモリ | 7,552 KB |
実行使用メモリ | 12,416 KB |
最終ジャッジ日時 | 2024-10-12 01:58:10 |
合計ジャッジ時間 | 3,580 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 10 WA * 10 |
コンパイルメッセージ
Syntax OK
ソースコード
n, m = gets.split(" ").map{|s| s.to_i} f = Array.new(n) {Array.new(n, false)} class UnionFind def initialize(n) @par = 0.upto(n-1).to_a @rank = Array.new(n, 0) end def unite(x, y) x = find(x) y = find(y) return if x == y if @rank[x] < @rank[y] then @par[x] = y else @par[y] = x @rank[x] += 1 if @rank[x] == @rank[y] end end def same?(x, y) find(x) == find(y) end private def find(x) if @par[x] == x then x else @par[x] = find(@par[x]) end end end uf = UnionFind.new(n) m.times { a, b = gets.split(" ").map{|s| s.to_i} f[a-1][b-1] = f[b-1][a-1] = true uf.unite(a-1, b-1) } cnt = 0 0.upto(n-1) {|a| (a+1).upto(n-1) {|b| (b+1).upto(n-1) {|c| cnt += 1 if (f[a][b] and f[b][c] and f[a][c]) or (f[a][b] and not uf.same?(b, c) and not uf.same?(a, c)) or (f[a][c] and not uf.same?(a, b) and not uf.same?(b, c)) or (f[b][c] and not uf.same?(a, b) and not uf.same?(a, c)) or (not uf.same?(a, b)and not uf.same?(a, c) and not uf.same?(b, c)) } } } puts cnt