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
AC × 12
TLE × 10
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