Submission #5500839


Source Code Expand

import java.util.Arrays;

public class Main {
  private static void solve() {
    int n = ni();
    int[] from = new int[n-1];
    int[] to = new int[n-1];
    for (int i = 0; i < n - 1; i ++) {
      from[i] = ni() - 1;
      to[i] = ni() - 1;
    }
    int[][] g = packU(n, from, to);
    
    int ret = dfs(0, new boolean[n], g);
    System.out.println(ret - 1);
  }
  
  private static int dfs(int now, boolean[] ved, int[][] g) {

    int[] dia = diameter(g, now, ved);
    ved[dia[3]] = true;
    int max = -1;
    
    for (int next : g[dia[3]]) {
      if (ved[next]) continue;
      max = Math.max(max, dfs(next, ved, g));
    }
    
    return max + 1;
  }
  
  public static int[][] packU(int n, int[] from, int[] to){ return packU(n, from, to, from.length); }
  public static int[][] packU(int n, int[] from, int[] to, int sup)
  {
      int[][] g = new int[n][];
      int[] p = new int[n];
      for(int i = 0;i < sup;i++)p[from[i]]++;
      for(int i = 0;i < sup;i++)p[to[i]]++;
      for(int i = 0;i < n;i++)g[i] = new int[p[i]];
      for(int i = 0;i < sup;i++){
          g[from[i]][--p[from[i]]] = to[i];
          g[to[i]][--p[to[i]]] = from[i];
      }
      return g;
  }

  
  public static int[] diameter(int[][] g, int v, boolean[] sved)
  {
      int n = g.length;
      int f0 = -1, f1 = -1, d01 = -1, c = -1;
      int[] q = new int[n];
      boolean[] ved = new boolean[n];
      {
          int qp = 0;
          q[qp++] = v; ved[0] = true;
          for(int i = 0;i < qp;i++){
              int cur = q[i];
              for(int e : g[cur]){
                  if(!ved[e] && !sved[e]){
                      ved[e] = true;
                      q[qp++] = e;
                      continue;
                  }
              }
          }
          f0 = q[qp-1];
      }
      {
          int[] d = new int[n];
          int qp = 0;
          Arrays.fill(ved, false);

          q[qp++] = f0; ved[f0] = true;
          for(int i = 0;i < qp;i++){
              int cur = q[i];
              for(int e : g[cur]){
                  if(!ved[e] && !sved[e]){
                      ved[e] = true;
                      q[qp++] = e;
                      d[e] = d[cur] + 1;
                      continue;
                  }
              }
          }
          f1 = q[qp-1];
          c = q[qp / 2];
          d01 = d[f1];
      }
      return new int[]{d01, f0, f1, c};
  }
  public static void main(String[] args) {
    new Thread(null, new Runnable() {
      @Override
      public void run() {
        long start = System.currentTimeMillis();
        String debug = args.length > 0 ? args[0] : null;
        if (debug != null) {
          try {
            is = java.nio.file.Files.newInputStream(java.nio.file.Paths.get(debug));
          } catch (Exception e) {
            throw new RuntimeException(e);
          }
        }
        reader = new java.io.BufferedReader(new java.io.InputStreamReader(is), 32768);
        solve();
        out.flush();
        tr((System.currentTimeMillis() - start) + "ms");
      }
    }, "", 64000000).start();
  }

  private static java.io.InputStream is = System.in;
  private static java.io.PrintWriter out = new java.io.PrintWriter(System.out);
  private static java.util.StringTokenizer tokenizer = null;
  private static java.io.BufferedReader reader;

  public static String next() {
    while (tokenizer == null || !tokenizer.hasMoreTokens()) {
      try {
        tokenizer = new java.util.StringTokenizer(reader.readLine());
      } catch (Exception e) {
        throw new RuntimeException(e);
      }
    }
    return tokenizer.nextToken();
  }

  private static double nd() {
    return Double.parseDouble(next());
  }

  private static long nl() {
    return Long.parseLong(next());
  }

  private static int[] na(int n) {
    int[] a = new int[n];
    for (int i = 0; i < n; i++)
      a[i] = ni();
    return a;
  }

  private static char[] ns() {
    return next().toCharArray();
  }

  private static long[] nal(int n) {
    long[] a = new long[n];
    for (int i = 0; i < n; i++)
      a[i] = nl();
    return a;
  }

  private static int[][] ntable(int n, int m) {
    int[][] table = new int[n][m];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        table[i][j] = ni();
      }
    }
    return table;
  }

  private static int[][] nlist(int n, int m) {
    int[][] table = new int[m][n];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        table[j][i] = ni();
      }
    }
    return table;
  }

  private static int ni() {
    return Integer.parseInt(next());
  }

  private static void tr(Object... o) {
    if (is != System.in)
      System.out.println(java.util.Arrays.deepToString(o));
  }
}

Submission Info

Submission Time
Task D - Uninity
User hiromi_ayase
Language Java8 (OpenJDK 1.8.0)
Score 0
Code Size 4924 Byte
Status WA
Exec Time 2114 ms
Memory 350440 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 1400
Status
AC × 2
AC × 5
WA × 7
TLE × 60
MLE × 2
Set Name Test Cases
Sample s1.txt, s2.txt
All 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, 37.txt, 38.txt, 39.txt, 40.txt, 41.txt, 42.txt, 43.txt, 44.txt, 45.txt, 46.txt, 47.txt, 48.txt, 49.txt, 50.txt, 51.txt, 52.txt, 53.txt, 54.txt, 55.txt, 56.txt, 57.txt, 58.txt, 59.txt, 60.txt, 61.txt, 62.txt, 63.txt, 64.txt, 65.txt, 66.txt, 67.txt, 68.txt, 69.txt, 70.txt, 71.txt, 72.txt, s1.txt, s2.txt
Case Name Status Exec Time Memory
01.txt TLE 2109 ms 165340 KB
02.txt TLE 2109 ms 153960 KB
03.txt TLE 2109 ms 221980 KB
04.txt TLE 2105 ms 153864 KB
05.txt TLE 2109 ms 169384 KB
06.txt TLE 2110 ms 276080 KB
07.txt TLE 2109 ms 223360 KB
08.txt TLE 2109 ms 157432 KB
09.txt TLE 2109 ms 345412 KB
10.txt TLE 2110 ms 343224 KB
11.txt MLE 1762 ms 344368 KB
12.txt MLE 1829 ms 342540 KB
13.txt TLE 2110 ms 346148 KB
14.txt TLE 2106 ms 346632 KB
15.txt TLE 2110 ms 346436 KB
16.txt TLE 2110 ms 347104 KB
17.txt TLE 2109 ms 155540 KB
18.txt TLE 2109 ms 156000 KB
19.txt TLE 2109 ms 152212 KB
20.txt TLE 2105 ms 156848 KB
21.txt TLE 2109 ms 157176 KB
22.txt TLE 2109 ms 152136 KB
23.txt TLE 2109 ms 155760 KB
24.txt TLE 2105 ms 159516 KB
25.txt TLE 2109 ms 155148 KB
26.txt TLE 2109 ms 156264 KB
27.txt TLE 2109 ms 154152 KB
28.txt TLE 2109 ms 155176 KB
29.txt TLE 2109 ms 156640 KB
30.txt TLE 2110 ms 275456 KB
31.txt TLE 2105 ms 154816 KB
32.txt TLE 2109 ms 267968 KB
33.txt TLE 2109 ms 276924 KB
34.txt TLE 2110 ms 276080 KB
35.txt TLE 2110 ms 275896 KB
36.txt TLE 2110 ms 341504 KB
37.txt TLE 2110 ms 341996 KB
38.txt TLE 2110 ms 343016 KB
39.txt TLE 2106 ms 344172 KB
40.txt TLE 2110 ms 349632 KB
41.txt TLE 2106 ms 350440 KB
42.txt TLE 2111 ms 342336 KB
43.txt TLE 2109 ms 344964 KB
44.txt TLE 2110 ms 348276 KB
45.txt TLE 2110 ms 344232 KB
46.txt TLE 2110 ms 346864 KB
47.txt TLE 2110 ms 344244 KB
48.txt TLE 2110 ms 346488 KB
49.txt TLE 2110 ms 346392 KB
50.txt TLE 2109 ms 345188 KB
51.txt TLE 2114 ms 345028 KB
52.txt TLE 2106 ms 346444 KB
53.txt TLE 2106 ms 345204 KB
54.txt TLE 2110 ms 345248 KB
55.txt TLE 2106 ms 347292 KB
56.txt TLE 2105 ms 158576 KB
57.txt TLE 2109 ms 275632 KB
58.txt TLE 2109 ms 273528 KB
59.txt TLE 2109 ms 343640 KB
60.txt TLE 2109 ms 342232 KB
61.txt TLE 2106 ms 343816 KB
62.txt TLE 2110 ms 344104 KB
63.txt WA 71 ms 18772 KB
64.txt WA 73 ms 19412 KB
65.txt WA 71 ms 19412 KB
66.txt AC 69 ms 18260 KB
67.txt AC 70 ms 20564 KB
68.txt WA 69 ms 18516 KB
69.txt WA 71 ms 19156 KB
70.txt WA 71 ms 20692 KB
71.txt WA 69 ms 21204 KB
72.txt AC 69 ms 19924 KB
s1.txt AC 70 ms 20948 KB
s2.txt AC 71 ms 20820 KB