K Path Query Codechef Solution | Codechef July Challenge 2021 | TechTalkBot

Code:- KPATHQRY
Name:- K Path Query
Codechef July 2021 long challenge

By TECHTALKBOT

You’re given a tree with  N N  vertices numbered from  1 1  to  N N . Your goal is to handle  Q Q  queries. For each query you are given  K K  nodes  v 1 , v 2 , … , v K v1,v2,…,vK . Find if there exists a simple path in the tree covering all the given vertices.

1. /* package codechef; // don't place package name! */
2.  
3. import java.util.*;
4. import java.lang.*;
5. import java.io.*;
6.  
7. /* Name of the class has to be "Main" only if the class is public. */
8. class Codechef {
9.  public static void main (String[] args) throws java.lang.Exception {
10.   // your code goes here
11.   Scanner sc = new Scanner(System.in);
12.  
13.   int T = sc.nextInt();
14.  
15.   while(T-- > 0) {
16.    int N = sc.nextInt();
17.    Map<Integer, Set<Integer>> tree = new HashMap<>();
18.    for(int i = 1; i < N; i++) addPath(tree, sc.nextInt(), sc.nextInt());
19.  
20.             int[] level = new int[N+1];
21.             int[] parent = new int[N+1];
22.    preProcess(tree, level, parent);
23.  
24.    int Q = sc.nextInt();
25.    int[] visited = new int[N+1];
26.    for(int i = 1; i <= Q; i++) {
27.     int K = sc.nextInt();
28.     int[] query = new int[K];
29.     int maxDepth = 0;
30.     int nodeWithMaxDepth = -1;
31.     for(int j = 0; j < K; j++) {
32.      query[j] = sc.nextInt();
33.      if(level[query[j]] > maxDepth) {
34.       maxDepth = level[query[j]];
35.       nodeWithMaxDepth = query[j];
36.      }
37.     }
38.  
39.     boolean hasPath = process(nodeWithMaxDepth, parent, level, query, visited, i);
40.     System.out.println(hasPath ? "YES" : "NO");
41.    }
42.   }
43.  
44.   sc.close();
45.  }
46.  
47.  private static boolean process(int nodeWithMaxDepth, int[] parent, int[] level, int[] query, int[] visited, int marker) {
48.   visitTillParent(nodeWithMaxDepth, parent, visited, marker);
49.   int maxDepth = 0;
50.   nodeWithMaxDepth = -1;
51.   for(int q : query) {
52.    if(visited[q] != marker && level[q] > maxDepth) {
53.     maxDepth = level[q];
54.     nodeWithMaxDepth = q;
55.    }
56.   }
57.  
58.   if(nodeWithMaxDepth == -1) return true;
59.  
60.   while(visited[nodeWithMaxDepth] != marker) {
61.    visited[nodeWithMaxDepth] = marker;
62.    nodeWithMaxDepth = parent[nodeWithMaxDepth];
63.   }
64.  
65.   for(int q : query) {
66.    if(visited[q] != marker || level[q] < level[nodeWithMaxDepth]) return false;
67.   }
68.   return true;
69.  }
70.  
71.  private static void visitTillParent(int nodeWithMaxDepth, int[] parent, int[] visited, int marker) {
72.   visited[nodeWithMaxDepth] = marker;
73.   while(parent[nodeWithMaxDepth] != -1) {
74.    nodeWithMaxDepth = parent[nodeWithMaxDepth];
75.    visited[nodeWithMaxDepth] = marker;
76.   }
77.  }
78.  
79.  private static void preProcess(Map<Integer, Set<Integer>> tree, int[] level, int[] parent) {
80.   boolean[] visited = new boolean[level.length];
81.   Queue<Integer> bfsQueue = new LinkedList<>();
82.  
83.         int u = 1;
84.   parent[u] = -1;
85.   level[u] = 0;
86.   bfsQueue.add(u);
87.   visited[u] = true;
88.  
89.   while(!bfsQueue.isEmpty()) {
90.    int n = bfsQueue.size();
91.    while(n-- > 0) {
92.     int parentNode = bfsQueue.poll();
93.     Set<Integer> children = tree.get(parentNode);
94.     for(Integer child : children) {
95.      if(!visited[child]) {
96.       parent[child] = parentNode;
97.       level[child] = level[parentNode]+1;
98.       visited[child] = true;
99.       bfsQueue.add(child);
100.      }
101.     }
102.    }
103.   }
104.  }
105.  
106.  private static void addPath(Map<Integer, Set<Integer>> tree, Integer u, Integer v) {
107.   addEdge(tree, u, v);
108.   addEdge(tree, v, u);
109.  }
110.  
111.  private static void addEdge(Map<Integer, Set<Integer>> tree, Integer u, Integer v) {
112.   if(!tree.containsKey(u)) tree.put(u, new HashSet<>());
113.   tree.get(u).add(v);
114.  }
115. }

• Maximum Production Codechef July Challenge 2021 Solution

• Relativity (RELATIVE) Codechef July Challenge 2021 Solution

• Codechef July Challenge 2021 Solution | XXOORR | TechTalkBot

• Optimal Denomination MinNotes Codechef July 2021 Challenge Solution TechTalkBot

•  K Path Query Codechef Solution | Codechef July Challenge 2021 | TechTalkBot