SHARE
TWEET

CF 253 Div1D

a guest Jun 19th, 2014 225 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.io.BufferedReader;
  2. import java.io.IOException;
  3. import java.io.InputStreamReader;
  4. import java.io.PrintWriter;
  5. import java.util.Arrays;
  6. import java.util.HashSet;
  7. import java.util.StringTokenizer;
  8.  
  9. /**
  10.  * Created by Aksenov239 on 16.06.2014.
  11.  */
  12. public class AdamAndTree {
  13.     public static void main(String[] args) {
  14.         new AdamAndTree().run();
  15.     }
  16.  
  17.     BufferedReader br;
  18.     StringTokenizer in;
  19.     PrintWriter out;
  20.  
  21.     public String nextToken() throws IOException {
  22.         while (in == null || !in.hasMoreTokens()) {
  23.             in = new StringTokenizer(br.readLine());
  24.         }
  25.  
  26.         return in.nextToken();
  27.     }
  28.  
  29.     public int nextInt() throws IOException {
  30.         return Integer.parseInt(nextToken());
  31.     }
  32.  
  33.     public void solve() throws IOException {
  34.         int n = nextInt();
  35.         int[] p = new int[n + 1];
  36.         int[] dp = new int[n + 1];
  37.         int[] max1 = new int[n + 1];
  38.         int[] max2 = new int[n + 1];
  39.         Arrays.fill(max1, -1);
  40.         Arrays.fill(max2, -1);
  41.  
  42.         p[0] = -1;
  43.  
  44.         for (int i = 0; i < n; i++) {
  45.             int x = nextInt() - 1;
  46.             p[i + 1] = x;
  47.             dp[i + 1] = 1;
  48.             int now = i + 1;
  49.             while (p[now] != -1) {
  50.                 if (dp[now] > max1[p[now]]) {
  51.                     max2[p[now]] = max1[p[now]];
  52.                     max1[p[now]] = dp[now];
  53.                 } else if (dp[now] > max2[p[now]]) {
  54.                     max2[p[now]] = dp[now];
  55.                 }
  56.  
  57.                 if (dp[p[now]] < Math.max(max1[p[now]], max2[p[now]] + 1)) {
  58.                     dp[p[now]] = Math.max(max1[p[now]], max2[p[now]] + 1);
  59.                 } else {
  60.                     break;
  61.                 }
  62.                 now = p[now];
  63.             }
  64.  
  65.             out.print(max1[0] + " ");
  66.         }
  67.  
  68.  
  69.     }
  70.  
  71.     public void run() {
  72.         try {
  73.             br = new BufferedReader(new InputStreamReader(System.in));
  74.             out = new PrintWriter(System.out);
  75.  
  76.             solve();
  77.  
  78.             out.close();
  79.         } catch (IOException e) {
  80.             e.printStackTrace();
  81.             System.exit(1);
  82.         }
  83.     }
  84. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top