Submission #700737


Source Code Expand

#!/usr/bin/ruby -w

class Solver
	def init()
		@n = gets.to_i;
		@dp = Array.new(@n + 1);
		@head = Array.new(@n + 1);
		@m = 0;
		@to = Array.new(@n * 2);
		@nxt = Array.new(@n * 2);
		@mod = 10**9 + 7;

		for i in 1..@n
			@dp[i] = Array.new(2, 1);
			@head[i] = -1;
		end
	end

	def add_edge(a, b)
		@to[@m] = b;
		@nxt[@m] = @head[a];
		@head[a] = @m;
		@m += 1;
	end

	def readData()
		init();

		i = 1;
		while i < @n do
			i += 1;
			str = gets.split(' ');
			a = str[0].to_i;
			b = str[1].to_i;
			add_edge(a, b);
			add_edge(b, a);
		end
	end

	def dfs(x, fa)
		i = @head[x];

		while i != -1 do
			j = @to[i];
			i = @nxt[i];
			if j == fa
				next;
			end
			dfs(j, x);
			@dp[x][0] = (@dp[j][0] + @dp[j][1]) % @mod * @dp[x][0] % @mod;
			@dp[x][1] = @dp[j][0] * @dp[x][1] % @mod;
		end
	end

	def output()
		puts (@dp[1][0]+@dp[1][1]) % @mod;
	end
end

solver = Solver.new();

solver.readData();
solver.dfs(1, 0);
solver.output();

Submission Info

Submission Time
Task D - 塗り絵
User hongrock
Language Ruby (2.3.3)
Score 100
Code Size 1006 Byte
Status AC
Exec Time 493 ms
Memory 13308 KB

Judge Result

Set Name All
Score / Max Score 100 / 100
Status
AC × 22
Set Name Test Cases
All 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
Case Name Status Exec Time Memory
000.txt AC 18 ms 1916 KB
001.txt AC 17 ms 1788 KB
002.txt AC 386 ms 12028 KB
003.txt AC 477 ms 13308 KB
004.txt AC 328 ms 11260 KB
005.txt AC 476 ms 13308 KB
006.txt AC 459 ms 12924 KB
007.txt AC 477 ms 13308 KB
008.txt AC 357 ms 11516 KB
009.txt AC 489 ms 13308 KB
010.txt AC 356 ms 11516 KB
011.txt AC 480 ms 13308 KB
012.txt AC 292 ms 8316 KB
013.txt AC 473 ms 13308 KB
014.txt AC 239 ms 7804 KB
015.txt AC 487 ms 13308 KB
016.txt AC 318 ms 10876 KB
017.txt AC 493 ms 13308 KB
018.txt AC 102 ms 4348 KB
019.txt AC 480 ms 13308 KB
020.txt AC 63 ms 3068 KB
021.txt AC 477 ms 13308 KB