Codeforces Round #361 (Div. 2) B

import java.io.*;
import java.util.*;
public class B1 {
 public static void main(String[] args) throws IOException{
  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  int n = Integer.parseInt(br.readLine());
  int[] a = new int[n+1];
  int[] dp = new int[n+1];
  StringTokenizer st = new StringTokenizer(br.readLine());
  for(int i = 1; i <= n; i++) { a[i] = Integer.parseInt(st.nextToken()); dp[i] = Integer.MAX_VALUE;}
  dp[1] = 0;
  LinkedList<Integer> q = new LinkedList<Integer>();
  q.add(1);
  int cur;
  while(!q.isEmpty()) {
   cur = q.removeFirst();
   if(dp[a[cur]] > dp[cur]+1) {dp[a[cur]] = dp[cur]+1; q.add(a[cur]);}
   if(cur > 1 && dp[cur-1] > dp[cur]+1) {dp[cur-1] = dp[cur]+1; q.add(cur-1);}
   if(cur < n && dp[cur+1] > dp[cur]+1) {dp[cur+1] = dp[cur]+1; q.add(cur+1);}
  }
  for(int i = 1; i <= n; i++) { if(i > 1) System.out.print(" "); System.out.print(dp[i]);}
  System.out.println();
 }
}

************

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Round361B {

 
 static int N;
 static ArrayList<Pair> adjList[];
 static class Pair implements Comparable<Pair>{
  int v,w;
  public Pair(int x, int y)
  {
   v = x;
   w = y;
  }
  
  public int compareTo(Pair p) {
   return w - p.w;
  }
  
  
 }
 
 // O((V+E)log(V))
 static int[] dijkstra(int s)
 {
  PriorityQueue<Pair> q = new PriorityQueue<Pair>();
  int dist[] = new int[N];
  Arrays.fill(dist, (int)1e9);
  dist[s] = 0;
  
  q.add(new Pair(s,0));
  while(!q.isEmpty())
  {
   Pair p = q.remove();
   if(p.w > dist[p.v])
    continue;
   
   for(Pair v : adjList[p.v])
    if(dist[p.v] + v.w < dist[v.v])
    {
     dist[v.v] = dist[p.v] + v.w;
     q.add(new Pair(v.v, dist[v.v]));
    }
   
  }
  return dist;
  
 }
 public static void main(String[] args) throws NumberFormatException, IOException {
  Scanner sc = new Scanner(System.in);
  N = sc.nextInt();
  adjList = new ArrayList[N];
  for(int i=0; i<N; i++)
   adjList[i] = new ArrayList<Pair>();
  
  int a[] = new int[N];
  Arrays.fill(a, (int)1e9);
  int b[] = new int[N];
  for(int i=0; i<N; i++){
   a[i] = sc.nextInt()-1;
   b[i] = i;
  }
  
  for(int i=0; i<N; i++)
  {
   adjList[i].add(new Pair(a[i],1));
  }
  
  for(int i=1; i<N; i++)
  {

   adjList[0].add(new Pair(i,b[i]));
   adjList[i].add(new Pair(0,b[i]));
   if(i < N-1)
   {
    adjList[i].add(new Pair(i+1,1));
    adjList[i+1].add(new Pair(i,1));
   }
  }
  
  int dist[] = dijkstra(0);
  
  PrintWriter out = new PrintWriter(System.out);
  for(int x : dist)
   out.print(x+" ");
  out.println();
  out.flush();
  out.close();
  
  
 }
 static class Scanner {
  BufferedReader br;
  StringTokenizer st;

  Scanner(FileReader f) {
   br = new BufferedReader(f);
  }

  public boolean ready() throws IOException {
   return br.ready();
  }

  Scanner(InputStream s) {
   br = new BufferedReader(new InputStreamReader(s));
  }

  String next() throws IOException {
   while (st == null || !st.hasMoreTokens())
    st = new StringTokenizer(br.readLine());
   return st.nextToken();
  }

  String nextLine() throws IOException {
   return br.readLine();
  }

  int nextInt() throws NumberFormatException, IOException {
   return Integer.parseInt(next());
  }

  long nextLong() throws NumberFormatException, IOException {
   return Long.parseLong(next());
  }
 }
}

**************

import java.io.*;
import java.util.*;
 
public class Main{
 
 
 public void solve(){
  int N = nextInt();
  int[] A = new int[N];
  int[] d = new int[N];
  for(int i = 0; i < N; i++){
   A[i] = nextInt() - 1;
   d[i] = -1;
  }
  Queue<Integer> queue = new ArrayDeque<>();
  d[0] = 0;
  queue.add(0);
  while(!queue.isEmpty()){
   int idx = queue.poll();
   int n;
   n = d[idx] + 1;
   int ni = idx + 1;
   if(ni < N && d[ni] == -1){
    d[ni] = n;
    queue.add(ni);
   }
   ni = idx - 1;
   if(ni >= 0 && d[ni] == -1){
    d[ni] = n;
    queue.add(ni);
   }
   ni = A[idx];
   if(ni >= 0 && d[ni] == -1){
    d[ni] = n;
    queue.add(ni);
   }
  }
  
  out.print(d[0]);
  for(int i = 1; i < N; i++){
   out.print(" ");
   out.print(d[i]);
  }
  out.println();
 }
 
 private static PrintWriter out;
 public static void main(String[] args){
  out = new PrintWriter(System.out);
  new Main().solve();
  out.flush();
 }
 
 
 
 public static int nextInt(){
  int num = 0;
  String str = next();
  boolean minus = false;
  int i = 0;
  if(str.charAt(0) == '-'){
   minus = true;
   i++;
  }
  int len = str.length();
  for(;i < len; i++){
   char c = str.charAt(i);
   if(!('0' <= c && c <= '9')) throw new RuntimeException();
   num = num * 10 + (c - '0');
  }
  return minus ? -num : num;
 }
 
 public static long nextLong(){
  long num = 0;
  String str = next();
  boolean minus = false;
  int i = 0;
  if(str.charAt(0) == '-'){
   minus = true;
   i++;
  }
  int len = str.length();
  for(;i < len; i++){
   char c = str.charAt(i);
   if(!('0' <= c && c <= '9')) throw new RuntimeException();
   num = num * 10l + (c - '0');
  }
  return minus ? -num : num;
 }
 public static String next(){
  int c;
  while(!isAlNum(c = read())){}
  StringBuilder build = new StringBuilder();
  build.append((char)c);
  while(isAlNum(c = read())){
   build.append((char)c);
  }
  return build.toString();
 }
 
 
 private static byte[] inputBuffer = new byte[1024];
 private static int bufferLength = 0;
 private static int bufferIndex = 0;
 private static int read(){
  if(bufferLength < 0) throw new RuntimeException();
  if(bufferIndex >= bufferLength){
   try{
    bufferLength = System.in.read(inputBuffer);
    bufferIndex = 0;
   }catch(IOException e){
    throw new RuntimeException(e);
   }
   if(bufferLength <= 0) return (bufferLength = -1);
  }
  return inputBuffer[bufferIndex++];
 }
 
 private static boolean isAlNum(int c){
  return '!' <= c && c <= '~';
 }
}


**********
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

/**
 * @author Don Li
 */
public class MikeShortcuts {

    void solve() {
        int n = in.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) a[i] = in.nextInt() - 1;

        int[] d = new int[n];
        Arrays.fill(d, -1);
        Queue<Integer> qu = new LinkedList<>();
        d[0] = 0;
        qu.offer(0);
        while (!qu.isEmpty()) {
            int i = qu.poll();
            if (i - 1 >= 0 && d[i - 1] == -1) {
                d[i - 1] = d[i] + 1;
                qu.offer(i - 1);
            }
            if (i + 1 < n && d[i + 1] == -1) {
                d[i + 1] = d[i] + 1;
                qu.offer(i + 1);
            }
            if (d[a[i]] == -1) {
                d[a[i]] = d[i] + 1;
                qu.offer(a[i]);
            }
        }

        for (int i = 0; i < n; i++) {
            if (i > 0) out.print(' ');
            out.print(d[i]);
        }
        out.println();
    }

    public static void main(String[] args) {
        in = new FastScanner(new BufferedReader(new InputStreamReader(System.in)));
        out = new PrintWriter(System.out);
        new MikeShortcuts().solve();
        out.close();
    }

    static FastScanner in;
    static PrintWriter out;

    static class FastScanner {
        BufferedReader in;
        StringTokenizer st;

        public FastScanner(BufferedReader in) {
            this.in = in;
        }

        public String nextToken() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(in.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(nextToken());
        }

        public long nextLong() {
            return Long.parseLong(nextToken());
        }

        public double nextDouble() {
            return Double.parseDouble(nextToken());
        }
    }
}
************

import java.io.*;
import java.util.*;
public class B1 {
 public static void main(String[] args) throws IOException{
  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  int n = Integer.parseInt(br.readLine());
  int[] a = new int[n+1];
  int[] dp = new int[n+1];
  StringTokenizer st = new StringTokenizer(br.readLine());
  for(int i = 1; i <= n; i++) { a[i] = Integer.parseInt(st.nextToken()); dp[i] = Integer.MAX_VALUE;}
  dp[1] = 0;
  LinkedList<Integer> q = new LinkedList<Integer>();
  q.add(1);
  int cur;
  while(!q.isEmpty()) {
   cur = q.removeFirst();
   if(dp[a[cur]] > dp[cur]+1) {dp[a[cur]] = dp[cur]+1; q.add(a[cur]);}
   if(cur > 1 && dp[cur-1] > dp[cur]+1) {dp[cur-1] = dp[cur]+1; q.add(cur-1);}
   if(cur < n && dp[cur+1] > dp[cur]+1) {dp[cur+1] = dp[cur]+1; q.add(cur+1);}
  }
  for(int i = 1; i <= n; i++) { if(i > 1) System.out.print(" "); System.out.print(dp[i]);}
  System.out.println();
 }
}