SHARE
TWEET

MilkVisits

a guest Dec 14th, 2019 124 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.util.*;
  2. import java.io.*;
  3.  
  4. class Graph {
  5.     private Map<Integer, Node> nodes = new HashMap<Integer, Node>();
  6.  
  7.     public Graph() {
  8.     }
  9.  
  10.     public void addEdge(Integer nodeName1, Integer nodeName2) {
  11.         Node node1 = nodes.get(nodeName1);
  12.         if (node1 == null) {
  13.             node1 = new Node(nodeName1);
  14.         }
  15.  
  16.         Node node2 = nodes.get(nodeName2);
  17.         if (node2 == null) {
  18.             node2 = new Node(nodeName2);
  19.         }
  20.  
  21.         node1.addNeighbor(node2);
  22.         node2.addNeighbor(node1);
  23.  
  24.         nodes.put(nodeName1, node1);
  25.         nodes.put(nodeName2, node2);
  26.     }
  27.  
  28.     public List<Integer> shortestPath(Integer startNodeName, Integer endNodeName) {
  29.         Map<Integer, Integer> parents = new HashMap<Integer, Integer>();
  30.         List<Node> temp = new ArrayList<Node>();
  31.  
  32.         Node start = nodes.get(startNodeName);
  33.         temp.add(start);
  34.         parents.put(startNodeName, null);
  35.  
  36.         while (temp.size() > 0) {
  37.             Node currentNode = temp.get(0);
  38.             List<Node> neighbors = currentNode.getNeighbors();
  39.  
  40.             for (int i = 0; i < neighbors.size(); i++) {
  41.                 Node neighbor = neighbors.get(i);
  42.                 Integer nodeName = neighbor.getName();
  43.                 boolean visited = parents.containsKey(nodeName);
  44.                 if (visited) {
  45.                     continue;
  46.                 } else {
  47.                     temp.add(neighbor);
  48.                     parents.put(nodeName, currentNode.getName());
  49.                     if (nodeName.equals(endNodeName)) {
  50.                         // System.out.println(parents);
  51.                         return getPath(parents, endNodeName);
  52.                     }
  53.                 }
  54.             }
  55.  
  56.             temp.remove(0);
  57.         }
  58.  
  59.         return null;
  60.     }
  61.  
  62.     private List<Integer> getPath(Map<Integer, Integer> parents, Integer endNodeName) {
  63.         List<Integer> path = new ArrayList<Integer>();
  64.         Integer node = endNodeName;
  65.         while (node != null) {
  66.             path.add(0, node);
  67.             Integer parent = parents.get(node);
  68.             node = parent;
  69.         }
  70.         return path;
  71.     }
  72. }
  73.  
  74. class Node {
  75.     Integer name;
  76.     List<Node> neighbors = new ArrayList<Node>();
  77.  
  78.     public Node(Integer name) {
  79.         this.name = name;
  80.     }
  81.  
  82.     public Integer getName() {
  83.         return this.name;
  84.     }
  85.  
  86.     public void addNeighbor(Node neighbor) {
  87.         neighbors.add(neighbor);
  88.     }
  89.  
  90.     public List<Node> getNeighbors() {
  91.         return neighbors;
  92.     }
  93.  
  94.     public String toString() {
  95.         return Integer.toString(this.name);
  96.     }
  97. }
  98.  
  99. class FastScanner {
  100.     public BufferedReader br;
  101.     public StringTokenizer st;
  102.  
  103.     public FastScanner(InputStream is) throws IOException {
  104.         br = new BufferedReader(new InputStreamReader(is), 32768);
  105.         st = null;
  106.     }
  107.  
  108.     public String next() {
  109.         while (st == null || !st.hasMoreTokens()) {
  110.             try {
  111.                 st = new StringTokenizer(br.readLine());
  112.             } catch (IOException e) {
  113.                 throw new RuntimeException(e);
  114.             }
  115.         }
  116.         return st.nextToken();
  117.     }
  118.  
  119.     public int nextInt() {
  120.         return Integer.parseInt(next());
  121.     }
  122.  
  123.     public long nextLong() {
  124.         return Long.parseLong(next());
  125.     }
  126.  
  127.     public double nextDouble() {
  128.         return Double.parseDouble(next());
  129.     }
  130.  
  131.     public String nextLine() {
  132.         String str = "";
  133.         try {
  134.             str = br.readLine();
  135.         } catch (IOException e) {
  136.             throw new RuntimeException(e);
  137.         }
  138.         return str;
  139.     }
  140. }
  141.  
  142. public class Main {
  143.     public static void main(String[] args) throws IOException {
  144.         InputStream is = new FileInputStream("milkvisits.in");
  145.         PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter("milkvisits.out")));
  146.         FastScanner sc = new FastScanner(is);
  147.  
  148.         int N = sc.nextInt();
  149.         int M = sc.nextInt();
  150.         int[] types = new int[N];
  151.         Graph g = new Graph();
  152.         int[] fr = new int[M];
  153.  
  154.         for (int i = 0; i < N; i++) {
  155.             types[i] = sc.nextInt();
  156.         }
  157.  
  158.         for (int i = 0; i < N - 1; i++) {
  159.             g.addEdge(sc.nextInt(), sc.nextInt());
  160.         }
  161.         int n1, n2, cow;
  162.         List<Integer> path;
  163.         for (int i = 0; i < M; i++) {
  164.             n1 = sc.nextInt();
  165.             n2 = sc.nextInt();
  166.             cow = sc.nextInt();
  167.             if (n1 == n2) {
  168.                 if (cow == types[n1 - 1]) {
  169.                     fr[i] = 1;
  170.                 }
  171.                 continue;
  172.             }
  173.             path = g.shortestPath(n1, n2);
  174.             if (check(path, types, cow)) {
  175.                 fr[i] = 1;
  176.             }
  177.         }
  178.         String out = "";
  179.         for (int i : fr) {
  180.             out += i;
  181.         }
  182.         System.out.println(out);
  183.         pw.write(out);
  184.         pw.close();
  185.     }
  186.  
  187.     public static boolean check(List<Integer> path, int[] s, int cow) {
  188.         for (int i : path) {
  189.             if (s[i - 1] == cow) {
  190.                 return true;
  191.             }
  192.         }
  193.         return false;
  194.     }
  195.  
  196.     private static void print(int[] arr) {
  197.         for (int i = 0; i < arr.length; i++) {
  198.             System.out.print(arr[i] + " ");
  199.         }
  200.         System.out.println();
  201.     }
  202. }
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