Submission #5500970


Source Code Expand

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);
    
    ved1 = new int[n];
    ved2 = new int[n];
    q = new int[n];
    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;
  }

  
  private static int[] ved1;
  private static int[] ved2;
  private static int cnt = 1;
  private static int[] q;
  public static int[] diameter(int[][] g, int v, boolean[] sved)
  {
    cnt ++;
      int f0 = -1, f1 = -1, d01 = -1, c = -1;
      {
          int qp = 0;
          q[qp++] = v; ved1[0] = cnt;
          for(int i = 0;i < qp;i++){
              int cur = q[i];
              for(int e : g[cur]){
                  if(ved1[e] != cnt && !sved[e]){
                      ved1[e] = cnt;
                      q[qp++] = e;
                      continue;
                  }
              }
          }
          f0 = q[qp-1];
      }
      {
          int qp = 0;

          q[qp++] = f0; ved2[f0] = cnt;
          for(int i = 0;i < qp;i++){
              int cur = q[i];
              for(int e : g[cur]){
                  if(ved2[e] != cnt && !sved[e]){
                      ved2[e] = cnt;
                      q[qp++] = e;
                      continue;
                  }
              }
          }
          f1 = q[qp-1];
          c = q[qp / 2];
      }
      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 4882 Byte
Status WA
Exec Time 2109 ms
Memory 51908 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 1400
Status
AC × 2
AC × 5
WA × 30
TLE × 39
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 2108 ms 40944 KB
02.txt TLE 2105 ms 44272 KB
03.txt TLE 2108 ms 43184 KB
04.txt TLE 2108 ms 43896 KB
05.txt TLE 2108 ms 42580 KB
06.txt TLE 2108 ms 43904 KB
07.txt TLE 2108 ms 42452 KB
08.txt TLE 2105 ms 39796 KB
09.txt WA 297 ms 40300 KB
10.txt WA 302 ms 38648 KB
11.txt WA 205 ms 32968 KB
12.txt WA 193 ms 34052 KB
13.txt WA 358 ms 44532 KB
14.txt WA 338 ms 40316 KB
15.txt WA 391 ms 43488 KB
16.txt WA 462 ms 42076 KB
17.txt TLE 2108 ms 41340 KB
18.txt TLE 2109 ms 44276 KB
19.txt TLE 2108 ms 44272 KB
20.txt TLE 2108 ms 40712 KB
21.txt TLE 2108 ms 42088 KB
22.txt TLE 2109 ms 39356 KB
23.txt TLE 2108 ms 43872 KB
24.txt TLE 2109 ms 40384 KB
25.txt TLE 2108 ms 43116 KB
26.txt TLE 2109 ms 39836 KB
27.txt TLE 2108 ms 42708 KB
28.txt TLE 2109 ms 44156 KB
29.txt TLE 2108 ms 43132 KB
30.txt TLE 2108 ms 44752 KB
31.txt TLE 2108 ms 44784 KB
32.txt TLE 2109 ms 42224 KB
33.txt TLE 2108 ms 44556 KB
34.txt TLE 2109 ms 40824 KB
35.txt TLE 2108 ms 42864 KB
36.txt TLE 2109 ms 38400 KB
37.txt TLE 2109 ms 42028 KB
38.txt TLE 2108 ms 40392 KB
39.txt TLE 2108 ms 43888 KB
40.txt WA 1941 ms 49356 KB
41.txt WA 1422 ms 46956 KB
42.txt TLE 2109 ms 38776 KB
43.txt TLE 2105 ms 44716 KB
44.txt WA 1856 ms 51908 KB
45.txt TLE 2105 ms 49372 KB
46.txt WA 1571 ms 48060 KB
47.txt WA 1970 ms 49400 KB
48.txt WA 1143 ms 50344 KB
49.txt WA 1468 ms 47760 KB
50.txt WA 1323 ms 45180 KB
51.txt WA 1406 ms 47712 KB
52.txt WA 1011 ms 47680 KB
53.txt WA 1199 ms 46816 KB
54.txt WA 1145 ms 43704 KB
55.txt WA 973 ms 48136 KB
56.txt TLE 2109 ms 44320 KB
57.txt TLE 2109 ms 44036 KB
58.txt TLE 2108 ms 37704 KB
59.txt WA 859 ms 43092 KB
60.txt WA 846 ms 44328 KB
61.txt TLE 2108 ms 40648 KB
62.txt TLE 2108 ms 44400 KB
63.txt WA 69 ms 19924 KB
64.txt WA 69 ms 19284 KB
65.txt WA 68 ms 21136 KB
66.txt AC 71 ms 19280 KB
67.txt AC 71 ms 21204 KB
68.txt WA 71 ms 22868 KB
69.txt WA 70 ms 21332 KB
70.txt WA 71 ms 22740 KB
71.txt WA 70 ms 22484 KB
72.txt AC 71 ms 23380 KB
s1.txt AC 69 ms 19924 KB
s2.txt AC 70 ms 21264 KB