結果

問題 No.1147 土偶Ⅱ
ユーザー 小野寺健小野寺健
提出日時 2021-11-02 20:24:15
言語 Ruby
(3.3.0)
結果
WA  
実行時間 -
コード長 1,035 bytes
コンパイル時間 39 ms
コンパイル使用メモリ 7,552 KB
実行使用メモリ 12,544 KB
最終ジャッジ日時 2024-04-20 06:50:26
合計ジャッジ時間 3,401 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 AC 72 ms
12,288 KB
testcase_02 AC 75 ms
12,288 KB
testcase_03 AC 71 ms
12,160 KB
testcase_04 AC 84 ms
12,288 KB
testcase_05 WA -
testcase_06 AC 105 ms
12,288 KB
testcase_07 WA -
testcase_08 WA -
testcase_09 AC 96 ms
12,288 KB
testcase_10 AC 84 ms
12,416 KB
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 AC 101 ms
12,416 KB
testcase_16 AC 82 ms
12,416 KB
testcase_17 AC 74 ms
12,288 KB
testcase_18 WA -
testcase_19 AC 105 ms
12,544 KB
testcase_20 AC 72 ms
12,288 KB
testcase_21 WA -
testcase_22 AC 91 ms
12,288 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
Syntax OK

ソースコード

diff # 

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
0