hqt

Untitled

hqt
Oct 1st, 2013
184
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 3.42 KB | None | 0 0
  1. import java.io.BufferedReader;
  2. import java.io.BufferedWriter;
  3. import java.io.File;
  4. import java.io.IOException;
  5. import java.io.InputStream;
  6. import java.io.InputStreamReader;
  7. import java.io.OutputStreamWriter;
  8. import java.io.PrintWriter;
  9. import java.math.BigInteger;
  10. import java.util.ArrayList;
  11. import java.util.List;
  12. import java.util.Scanner;
  13. import java.util.StringTokenizer;
  14.  
  15. /**
  16.  * <b> Algorithm on Codeforces. Problem C div 2 </b> </br>
  17.  * @author Huynh Quang Thao
  18.  *
  19.  */
  20. public class Main {
  21.  
  22.     public static void main(String[] args) throws Exception {
  23.         Main main = new Main();
  24.         main.run();
  25.     }
  26.    
  27.     public void run() throws Exception {
  28.          Scanner sc = null;
  29.          PrintWriter pr = null;
  30.  
  31.          pr=new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
  32.          sc = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
  33.        //  sc = new Scanner(new File("input.txt"));
  34.          
  35.          int n = sc.nextInt();
  36.  
  37.          int[] revpath = new int[n+1];
  38.          int[] type = new int[n+1];
  39.          int[] count = new int[n+1];
  40.          int[] path = new int[n+1];
  41.          
  42.          for (int i = 1; i <= n; i++) type[i] = sc.nextInt();
  43.          for (int i = 1; i <= n; i++) {
  44.             int a = sc.nextInt();
  45.             // exist path from a to i
  46.             path[a] = i;
  47.             count[a]++;
  48.          }
  49.          
  50.          // building rev-path
  51.          for (int i = 1; i <= n; i++) {
  52.              int to = path[i];
  53.              if (count[i] == 1) revpath[to] = i;
  54.          }
  55.          
  56.         /* for (int i = 1; i <= n; i++) {
  57.              System.out.println(path[i]);
  58.          }
  59.          System.out.println("---------");
  60.          
  61.          for (int i = 1; i <= n; i++) {
  62.              System.out.println(revpath[i]);
  63.          }*/
  64.          
  65.        
  66.          // dfs from hotel
  67.          List<Integer> resList = new ArrayList<Integer>();
  68.          for (int i = 1; i <= n; i++) {
  69.              if (type[i] == 1) {
  70.                  int v = i;
  71.                  // dfs from v - vertex
  72.                  List<Integer> list = new ArrayList<Integer>();
  73.                  list.add(v);
  74.                  while (revpath[v] != 0) {
  75.                      v = revpath[v];
  76.                      list.add(v);
  77.                  }
  78.                  if (list.size() > resList.size()) resList = list;
  79.              }
  80.          }
  81.          
  82.          System.out.printf("%d\n", resList.size());
  83.          for (int i = resList.size()-1; i >= 0; i--) System.out.printf("%d ", resList.get(i));
  84.          
  85.          pr.close();
  86.          sc.close();
  87.     }
  88.    
  89.     public void dfs(int v) {
  90.        
  91.     }
  92.    
  93.    
  94.     static class Team {
  95.         int baloon;
  96.         int rA;
  97.         int rB;
  98.         public Team(int baloon, int rA, int rB) {
  99.             this.baloon = baloon;
  100.             this.rA = rA;
  101.             this.rB = rB;
  102.         }
  103.     }
  104.  
  105.     static class InputReader {
  106.         public BufferedReader reader;
  107.  
  108.         public StringTokenizer tokenizer;
  109.  
  110.         public InputReader(InputStream stream) {
  111.             reader = new BufferedReader(new InputStreamReader(stream));
  112.             tokenizer = null;
  113.         }
  114.  
  115.         public String next() {
  116.             while (tokenizer == null || !tokenizer.hasMoreTokens()) {
  117.                 try {
  118.                     tokenizer = new StringTokenizer(reader.readLine());
  119.                 }
  120.                 catch (IOException e) {
  121.                     throw new RuntimeException(e);
  122.                 }
  123.             }
  124.             return tokenizer.nextToken();
  125.         }
  126.  
  127.         public int nextInt() {
  128.             return Integer.parseInt(next());
  129.         }
  130.  
  131.         public double nextDouble() {
  132.             return Double.parseDouble(next());
  133.         }
  134.  
  135.         public float nextFloat() {
  136.             return Float.parseFloat(next());
  137.         }
  138.  
  139.         public long nextLong() {
  140.             return Long.parseLong(next());
  141.         }
  142.  
  143.         public BigInteger nextBigInteger() {
  144.             return new BigInteger(next());
  145.         }
  146.  
  147.     }
  148. }
Advertisement
Add Comment
Please, Sign In to add comment