fork download
  1. import java.util.ArrayList;
  2. import java.util.List;
  3.  
  4. public class Main implements Runnable {
  5. public static void main(String[] args) {
  6. new Thread(null, new Main(), "", 256 * (1L << 20)).start();
  7. }
  8.  
  9. @Override
  10. public void run() {
  11. int n = 500000;
  12. List<Integer>[] g = new List[n];
  13. for (int i = 0; i < n; i++) {
  14. g[i] = new ArrayList<>();
  15. }
  16. for (int i = 1; i < n; i++) {
  17. int p = i - 1;
  18. g[i].add(p);
  19. g[p].add(i);
  20. }
  21.  
  22. long t1 = System.nanoTime();
  23. for (int i = 0; i < 100000; i++) {
  24. dfs(0, -1, g, 0, 0); // JIT please
  25. }
  26. int result = dfs(0, -1, g, 0, Integer.MAX_VALUE);
  27. long t2 = System.nanoTime();
  28. System.out.println("time = " + (t2 - t1) / 1.0e9 + " sec, result = " + result);
  29. }
  30.  
  31. private int dfs(int x, int p, List<Integer>[] g, int curDepth, int maxDepth) {
  32. if (curDepth > maxDepth) {
  33. return 0;
  34. }
  35. int result = 1;
  36. for (int y : g[x]) {
  37. if (y == p) {
  38. continue;
  39. }
  40. result += dfs(y, x, g, curDepth + 1, maxDepth);
  41. }
  42. return result;
  43. }
  44. }
Success #stdin #stdout 0.24s 153552KB
stdin
Standard input is empty
stdout
time = 0.049763821 sec, result = 500000