AtCoder Beginner Contest 036

Submission #761133

Source codeソースコード


# (1) 頂点どうしの関係性を配列に入力する。隣接点のデータを作成する

n = gets.to_i

@neighbor = []
# 関数f, gの中から参照するので、@をつけてインスタンス変数にして、サブクラスから参照可能にする
$mod  = (10**9 + 7)
n.times do
	@neighbor << []
end

(n-1).times do
	line = gets.split
	i = line[0].to_i
	j = line[1].to_i

	@neighbor[i-1] << j-1
	@neighbor[j-1] << i-1
end

def f(x, p)
	# f(x, p) = 頂点xを根とした部分木に対する独立集合の個数
	# g(x,p) = 上記のうち、頂点xを含まないものの個数
	# pはxの親とする
	# 関数の返り値は[g(x,p), f(x,p)]である
	f_product = 1
	g_product = 1

	for i in @neighbor[x]
		if i == p
			next
		else
			temp = f(i,x)
			f_product *= temp[0]
			g_product *= temp[1]
		end
	end
	
	return [g_product % $mod , (g_product + f_product) % $mod]
end

p f(0,-1)[1]

Submission

Task問題 D - 塗り絵
User nameユーザ名 ライナス
Created time投稿日時
Language言語 Ruby (2.3.3)
Status状態 AC
Score得点 100
Source lengthソースコード長 953 Byte
File nameファイル名
Exec time実行時間 340 ms
Memory usageメモリ使用量 11644 KB

Test case

Set

Set name Score得点 / Max score Cases
All 100 / 100 000.txt,001.txt,002.txt,003.txt,004.txt,005.txt,006.txt,007.txt,008.txt,009.txt,010.txt,011.txt,012.txt,013.txt,014.txt,015.txt,016.txt,017.txt,018.txt,019.txt,020.txt,021.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
000.txt AC 17 ms 1788 KB
001.txt AC 17 ms 1788 KB
002.txt AC 266 ms 10620 KB
003.txt AC 334 ms 11516 KB
004.txt AC 229 ms 9724 KB
005.txt AC 340 ms 11644 KB
006.txt AC 311 ms 11260 KB
007.txt AC 332 ms 11516 KB
008.txt AC 242 ms 10236 KB
009.txt AC 335 ms 11516 KB
010.txt AC 247 ms 10236 KB
011.txt AC 334 ms 11388 KB
012.txt AC 207 ms 7420 KB
013.txt AC 339 ms 11516 KB
014.txt AC 171 ms 7164 KB
015.txt AC 339 ms 11644 KB
016.txt AC 217 ms 9596 KB
017.txt AC 333 ms 11388 KB
018.txt AC 77 ms 4092 KB
019.txt AC 335 ms 11516 KB
020.txt AC 50 ms 3068 KB
021.txt AC 335 ms 11516 KB