rakcode1998

Untitled

Feb 17th, 2017
305
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 7.18 KB | None | 0 0
  1. package Codeforces;
  2.  
  3. import java.io.DataInputStream;
  4. import java.io.FileInputStream;
  5. import java.io.IOException;
  6. import java.io.OutputStream;
  7. import java.io.PrintWriter;
  8. import java.util.Iterator;
  9. import java.util.TreeSet;
  10.  
  11. /**
  12.  * Created by rakshit on 11/2/17.
  13.  * Java is Love , 4 Forces.. :)
  14.  */
  15. public class Party {
  16.  
  17.     static class Reader
  18.     {
  19.         final private int BUFFER_SIZE = 1 << 16;
  20.         private DataInputStream din;
  21.         private byte[] buffer;
  22.         private int bufferPointer, bytesRead;
  23.  
  24.         public Reader()
  25.         {
  26.             din = new DataInputStream(System.in);
  27.             buffer = new byte[BUFFER_SIZE];
  28.             bufferPointer = bytesRead = 0;
  29.         }
  30.  
  31.         public Reader(String file_name) throws IOException
  32.         {
  33.             din = new DataInputStream(new FileInputStream(file_name));
  34.             buffer = new byte[BUFFER_SIZE];
  35.             bufferPointer = bytesRead = 0;
  36.         }
  37.  
  38.         public String readLine() throws IOException
  39.         {
  40.             byte[] buf = new byte[64]; // line length
  41.             int cnt = 0, c;
  42.             while ((c = read()) != -1)
  43.             {
  44.                 if (c == '\n')
  45.                     break;
  46.                 buf[cnt++] = (byte) c;
  47.             }
  48.             return new String(buf, 0, cnt);
  49.         }
  50.  
  51.         public int nextInt() throws IOException
  52.         {
  53.             int ret = 0;
  54.             byte c = read();
  55.             while (c <= ' ')
  56.                 c = read();
  57.             boolean neg = (c == '-');
  58.             if (neg)
  59.                 c = read();
  60.             do
  61.             {
  62.                 ret = ret * 10 + c - '0';
  63.             }  while ((c = read()) >= '0' && c <= '9');
  64.  
  65.             if (neg)
  66.                 return -ret;
  67.             return ret;
  68.         }
  69.  
  70.         public long nextLong() throws IOException
  71.         {
  72.             long ret = 0;
  73.             byte c = read();
  74.             while (c <= ' ')
  75.                 c = read();
  76.             boolean neg = (c == '-');
  77.             if (neg)
  78.                 c = read();
  79.             do {
  80.                 ret = ret * 10 + c - '0';
  81.             }
  82.             while ((c = read()) >= '0' && c <= '9');
  83.             if (neg)
  84.                 return -ret;
  85.             return ret;
  86.         }
  87.  
  88.         public double nextDouble() throws IOException
  89.         {
  90.             double ret = 0, div = 1;
  91.             byte c = read();
  92.             while (c <= ' ')
  93.                 c = read();
  94.             boolean neg = (c == '-');
  95.             if (neg)
  96.                 c = read();
  97.  
  98.             do {
  99.                 ret = ret * 10 + c - '0';
  100.             }
  101.             while ((c = read()) >= '0' && c <= '9');
  102.  
  103.             if (c == '.')
  104.             {
  105.                 while ((c = read()) >= '0' && c <= '9')
  106.                 {
  107.                     ret += (c - '0') / (div *= 10);
  108.                 }
  109.             }
  110.  
  111.             if (neg)
  112.                 return -ret;
  113.             return ret;
  114.         }
  115.  
  116.         private void fillBuffer() throws IOException
  117.         {
  118.             bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
  119.             if (bytesRead == -1)
  120.                 buffer[0] = -1;
  121.         }
  122.  
  123.         private byte read() throws IOException
  124.         {
  125.             if (bufferPointer == bytesRead)
  126.                 fillBuffer();
  127.             return buffer[bufferPointer++];
  128.         }
  129.  
  130.         public void close() throws IOException
  131.         {
  132.             if (din == null)
  133.                 return;
  134.             din.close();
  135.         }
  136.     }
  137.     public static void main(String args[]) throws IOException
  138.     {
  139.         OutputStream outputstream=System.out;
  140.         Reader in=new Reader();
  141.         PrintWriter out=new PrintWriter (outputstream);
  142.         Task solver=new Task();
  143.         solver.solve(in,out);
  144.         in.close();
  145.     }
  146.  
  147.     static class Task
  148.     {
  149.         public final int k=123456;
  150.         public static final int mod=1000000007;
  151.         TreeSet<Integer>a[]=new TreeSet[2222];
  152.         public void solve(Reader in , PrintWriter out) throws IOException
  153.         {
  154.             int n=in.nextInt();
  155.             int c;
  156.  
  157.             for(int i=0;i<=n;i++)
  158.             {
  159.                 a[i]=new TreeSet<>();
  160.             }
  161.  
  162.             for(int i=1;i<=n;i++)
  163.             {
  164.                 c=in.nextInt();
  165.                 if(c!=-1)
  166.                 {
  167.                     a[c].add(i);
  168.                 }
  169.             }
  170.  
  171.             done(n);
  172.             int res=1;
  173.  
  174.             TreeSet<Integer>store=new TreeSet<>();
  175.  
  176.             for(int i=1;i<=n;i++)
  177.             {
  178.                 store.add(i);
  179.             }
  180.  
  181.             TreeSet<Integer>repeat=new TreeSet<>();
  182.  
  183.             for(int i=1;i<=n;i++)
  184.             {
  185.                 if(a[i].size()!=0)
  186.                 {
  187.                     repeat.add(i);
  188.                     store.remove(i);
  189.  
  190.                     Iterator<Integer>h=store.iterator();
  191.  
  192.                     while(h.hasNext())
  193.                     {
  194.                         Integer q=h.next();
  195.                         if(!a[i].contains(q))
  196.                         {
  197.                             repeat.add(q);
  198.                             store.remove(q);
  199.                         }
  200.                     }
  201.  
  202.                     if(repeat.size()!=0)
  203.                     {
  204.                         res++;
  205.                         repeat.clear();
  206.                     }
  207.                 }
  208.             }
  209.  
  210.             out.println(res);
  211.             out.flush();
  212.         }
  213.  
  214.         private void done(int n)
  215.         {
  216.             for(int i=1;i<=n;i++)
  217.             {
  218.                 if(a[i].size()!=0)
  219.                 {
  220.                     Iterator<Integer> j=a[i].iterator();
  221.                     while(j.hasNext())
  222.                     {
  223.                         Integer q=j.next();
  224.                         if(a[q].size()!=0)
  225.                         {
  226.                             Iterator<Integer> p=a[q].iterator();
  227.                             while(p.hasNext())
  228.                             {
  229.                                 a[i].add(p.next());
  230.                             }
  231.                         }
  232.                     }
  233.                 }
  234.             }
  235.         }
  236.  
  237.         private static long gcd(long a,long b)
  238.         {
  239.             if(a==0)
  240.                 return b;
  241.             else
  242.                 return gcd(b%a,a);
  243.         }
  244.  
  245.         private static long lcm(long a, long b)
  246.         {
  247.             return (a*b)/gcd(a,b);
  248.         }
  249.  
  250.         private static boolean prime(int n)
  251.         {
  252.             if(n==1 || (n%2==0 && n!=2))
  253.                 return false;
  254.             else if(n==2 || n==3)
  255.             {
  256.                 return true;
  257.             }
  258.             else
  259.             {
  260.                 int res=0;
  261.                 for(int i=3;i<=(int)Math.sqrt(n) ;i+=2)
  262.                 {
  263.                     if(n%i==0)
  264.                     {
  265.                         res++;
  266.                         break;
  267.                     }
  268.                 }
  269.  
  270.                 if(res>0)
  271.                 {
  272.                     return false;
  273.                 }
  274.                 else
  275.                 {
  276.                     return true;
  277.                 }
  278.             }
  279.         }
  280.     }
  281. }
Add Comment
Please, Sign In to add comment