Submission #1294285
Source Code Expand
import java.util.ArrayList; import java.util.List; import java.util.Scanner; public class Main { public static void main(String[] args) { new Main().solve(); } int N; Long[] f; //iを根として塗れる数 Long[] g; //iが白で根として塗れる数 List<Edge>[] edge; int mod=(int)Math.pow(10, 9)+7; boolean used[]; void solve(){ Scanner sc=new Scanner(System.in); N=sc.nextInt(); f=new Long[N]; g=new Long[N]; edge=new List[N]; used=new boolean[N]; for(int i=0;i<N;i++)edge[i]=new ArrayList<Edge>(); for(int i=0;i<N-1;i++){ int a=sc.nextInt()-1; int b=sc.nextInt()-1; addEdge(a,b); addEdge(b,a); } dfs(0); System.out.println(f[0]); } void dfs(int s){ used[s]=true; long gg=1; long ff=1; for(Edge e:edge[s]){ if(used[e.to])continue; dfs(e.to); gg*=f[e.to]; ff*=g[e.to]; gg%=mod; ff%=mod; } ff+=(gg%mod); g[s]=gg%mod; f[s]=ff%mod; } void addEdge(int from,int to){ edge[from].add(new Edge(to,from)); } class Edge{ int to; int from; Edge(int to,int from){ this.to=to; this.from=from; } } }
Submission Info
Submission Time | |
---|---|
Task | D - 塗り絵 |
User | kwkm0429 |
Language | Java8 (OpenJDK 1.8.0) |
Score | 100 |
Code Size | 1177 Byte |
Status | AC |
Exec Time | 642 ms |
Memory | 107132 KB |
Compile Error
Note: ./Main.java uses unchecked or unsafe operations. Note: Recompile with -Xlint:unchecked for details.
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 | 93 ms | 21716 KB |
001.txt | AC | 93 ms | 21076 KB |
002.txt | AC | 560 ms | 74096 KB |
003.txt | AC | 639 ms | 103596 KB |
004.txt | AC | 539 ms | 71060 KB |
005.txt | AC | 642 ms | 104800 KB |
006.txt | AC | 604 ms | 92788 KB |
007.txt | AC | 621 ms | 103784 KB |
008.txt | AC | 537 ms | 72232 KB |
009.txt | AC | 620 ms | 106776 KB |
010.txt | AC | 542 ms | 70764 KB |
011.txt | AC | 621 ms | 104064 KB |
012.txt | AC | 505 ms | 68420 KB |
013.txt | AC | 635 ms | 104308 KB |
014.txt | AC | 452 ms | 66100 KB |
015.txt | AC | 633 ms | 107132 KB |
016.txt | AC | 524 ms | 69160 KB |
017.txt | AC | 608 ms | 104856 KB |
018.txt | AC | 317 ms | 44412 KB |
019.txt | AC | 624 ms | 102608 KB |
020.txt | AC | 251 ms | 45908 KB |
021.txt | AC | 621 ms | 105424 KB |