Submission #1513105
Source Code Expand
MOD = 1_000_000_007 N = gets.to_i R = Hash.new {|h, k| h[k] = []} (N - 1).times do a, b = gets.split.map(&:to_i) R[a] << b R[b] << a end C = [0, Array.new(N + 1), Array.new(N + 1)] # 1 : white # -1 : black def calc(node, from, color) return C[color][node] if C[color][node] if R[node].size == 1 && R[node][0] == from return C[color][node] = 1 else ans = 1 R[node].each do |x| next if x == from if color == 1 ans *= (calc(x, node, -1) + calc(x, node, 1)) else ans *= calc(x, node, 1) end ans %= MOD end return C[color][node] = ans end end puts (calc(1, 0, 1) + calc(1, 0, - 1)) % MOD
Submission Info
Submission Time | |
---|---|
Task | D - 塗り絵 |
User | hatovalley |
Language | Ruby (2.3.3) |
Score | 100 |
Code Size | 702 Byte |
Status | AC |
Exec Time | 409 ms |
Memory | 21012 KB |
Judge Result
Set Name | All | ||
---|---|---|---|
Score / Max Score | 100 / 100 | ||
Status |
|
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 | 7 ms | 1788 KB |
001.txt | AC | 7 ms | 1788 KB |
002.txt | AC | 304 ms | 16892 KB |
003.txt | AC | 368 ms | 18940 KB |
004.txt | AC | 248 ms | 12540 KB |
005.txt | AC | 377 ms | 19068 KB |
006.txt | AC | 358 ms | 20092 KB |
007.txt | AC | 398 ms | 18940 KB |
008.txt | AC | 271 ms | 14076 KB |
009.txt | AC | 392 ms | 18940 KB |
010.txt | AC | 274 ms | 14460 KB |
011.txt | AC | 405 ms | 18812 KB |
012.txt | AC | 225 ms | 11644 KB |
013.txt | AC | 370 ms | 18940 KB |
014.txt | AC | 173 ms | 12284 KB |
015.txt | AC | 386 ms | 18940 KB |
016.txt | AC | 229 ms | 11772 KB |
017.txt | AC | 374 ms | 18812 KB |
018.txt | AC | 69 ms | 4988 KB |
019.txt | AC | 409 ms | 18940 KB |
020.txt | AC | 40 ms | 3708 KB |
021.txt | AC | 371 ms | 21012 KB |