Submission #924250
Source Code Expand
import java.util.*; import java.util.function.BiFunction; public class Main { Scanner sc = new Scanner(System.in); public static void main(String[] args) { new Main().run(); } class Node { ArrayList<Node> list = new ArrayList<>(); ArrayList<Node> adj = new ArrayList<>(); int id; Node(int i) { id = i; } } long MOD = 1_000_000_007; long[] memoF; long f(Node node) { if (memoF[node.id] != 0) { return memoF[node.id]; } long white = g(node); long black = 1; for (Node c : node.list) { black *= g(c); black %= MOD; } long sum = white + black; sum %= MOD; memoF[node.id] = sum; debug("f", node.id, sum); return sum; } long[] memoG; long g(Node node) { if (memoG[node.id] != 0) { return memoG[node.id]; } long white = 1; for (Node c : node.list) { white *= f(c); white %= MOD; } debug("g", node.id, white); memoG[node.id] = white; return white; } void make(Node node, int n) { boolean[] done = new boolean[n + 1]; done[node.id] = true; Queue<Node> queue = new LinkedList<>(); queue.add(node); while (queue.size() > 0) { Node atom = queue.poll(); for (Node next : atom.adj) { if (done[next.id]) { continue; } done[next.id] = true; atom.list.add(next); queue.add(next); } } } void run() { int n = ni(); ArrayList<Node> list = new ArrayList<>(); for (int i = 0; i < n + 1; ++i) { list.add(new Node(i)); } for (int i = 0; i < n - 1; ++i) { int u = ni(); int v = ni(); list.get(u).adj.add(list.get(v)); list.get(v).adj.add(list.get(u)); } make(list.get(1), n); memoF = new long[n + 1]; memoG = new long[n + 1]; long ans = f(list.get(1)); System.out.println(ans); } int ni() { return Integer.parseInt(sc.next()); } void debug(Object... os) { System.err.println(Arrays.deepToString(os)); } class BIT<T> { int n; ArrayList<T> bit; BiFunction<T, T, T> bif; BIT(int n, BiFunction<T, T, T> bif, T defaultValue) { this.n = n; bit = new ArrayList<>(n + 1); for (int i = 0; i < n + 1; ++i) { bit.add(defaultValue); } this.bif = bif; } void update(int i, T v) { for (int x = i; x <= n; x += x & -x) { bit.set(x, bif.apply(bit.get(x), v)); } } T reduce(int i, T defaultValue) { T ret = defaultValue; for (int x = i; x > 0; x -= x & -x) { ret = bif.apply(ret, bit.get(x)); } return ret; } } }
Submission Info
Submission Time | |
---|---|
Task | D - 塗り絵 |
User | arukuka |
Language | Java8 (OpenJDK 1.8.0) |
Score | 0 |
Code Size | 2809 Byte |
Status | TLE |
Exec Time | 2111 ms |
Memory | 139892 KB |
Judge Result
Set Name | All | ||||
---|---|---|---|---|---|
Score / Max Score | 0 / 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 | 129 ms | 9556 KB |
001.txt | AC | 129 ms | 9552 KB |
002.txt | AC | 1890 ms | 133280 KB |
003.txt | TLE | 2111 ms | 139892 KB |
004.txt | AC | 1738 ms | 121840 KB |
005.txt | TLE | 2111 ms | 136716 KB |
006.txt | TLE | 2111 ms | 136256 KB |
007.txt | TLE | 2111 ms | 139092 KB |
008.txt | AC | 1768 ms | 127860 KB |
009.txt | AC | 1996 ms | 126380 KB |
010.txt | AC | 1690 ms | 126872 KB |
011.txt | TLE | 2111 ms | 137276 KB |
012.txt | AC | 1628 ms | 97508 KB |
013.txt | TLE | 2111 ms | 136320 KB |
014.txt | AC | 1423 ms | 93492 KB |
015.txt | TLE | 2111 ms | 139600 KB |
016.txt | AC | 1766 ms | 112040 KB |
017.txt | TLE | 2111 ms | 136296 KB |
018.txt | AC | 742 ms | 41388 KB |
019.txt | TLE | 2111 ms | 136388 KB |
020.txt | AC | 544 ms | 32560 KB |
021.txt | TLE | 2111 ms | 136728 KB |