HackerRank Travel in HackerLand Problem Solution Yashwant Parihar, June 1, 2023May 28, 2024 In this post, we will solve HackerRank Travel in HackerLand Problem Solution. HackerLand is a country with n beautiful cities and m undirected roads. Like every other beautiful country, HackerLand has traffic jams,Each road has a crowd value. The crowd value of a path is defined as the maximum crowd value for all roads in the path. For example, if the crowd values for all roads are[1, 4, 5, 6, 3], then the crowd value for the path will be max(1, 4, 5, 6, 3) = 6. Each city has a type value, T., denoting the type of buildings in the city.David just started his vacation in HackerLand. He wants to travel from city to city y. He also wants to see at least k different types of buildings along the path from a to y. When choosing a path from city a to city y that has at least k different types of buildings along the path, David always selects the one with the minimum crowd value.You will be given q queries. Each query takes the form of 3 space-separated integers, ₁, y₁ and k, denoting the respective values for starting city, destination city, and minimum number of unique buildings that David wants to see along the way. For each query, you must print the minimum crowd value for a path between, and y, that has at least k different buildings along the route. If there is no such path, print -1.Note: A path may contain cycles (i.e., the same roads or cities may be traveled more than once). Input FormatThe first line contains 3 space-separated integers denoting the respective values for n (the number of cities), m (the number of roads), and q (the number of queries).The second line contains n space-separated integers describing the respective building type for each city in array T (where the i-th value is T, and 1 ≤ i ≤n).Each of the m subsequent lines defines a road in the form of 3 space-separated integers,cy; and up, defining an undirected road with crowd value u; that connects cities andYi-Each of the q subsequent lines defines a query in the form of 3 space-separated integers, xj. yj, and kj (where 0 ≤ j < q), respectively. Output Format For each query, print its answer on a new line. Sample Input 7 6 1 1 1 4 5 1 3 2 1 2 3 2 6 2 2 3 4 3 4 3 2 4 9 5 7 9 1 2 4 Sample Output 4 Explanation The diagram below depicts the country given as Sample Input. Different values of are shown in different colors.The path for the last query (1 2 4) will be 1→2→3→4→3 →2→6 → 2. David sees his first type of building in cities 1 and 2. his second type of building in city 3. his third type of building in city 4. and his fourth type of building in city 6. The crowd values for each road traveled on this path are [3, 4, 3, 3, 4, 2, 2]; the maximum of these values is 4. Thus, we print 4 on a new line. HackerRank Travel in HackerLand Problem Solution Travel in HackerLand C Solution #include <stdio.h> #include <stdlib.h> typedef struct _tree_node{ enum {red,black} colour; int data; int idx; struct _tree_node *left,*right,*parent; }tree_node; tree_node *get_min(tree_node *root); void merge(tree_node *root,tree_node **m,int *s,int f); int get_group(int x); void update_group(int x,int y); void sort_a3(int*a,int*b,int*c,int size); void merge3(int*a,int*left_a,int*right_a,int*b,int*left_b,int*right_b,int*c,int*left_c,int*right_c,int left_size,int right_size); void left_rotate(tree_node **root,tree_node *x); void right_rotate(tree_node **root,tree_node *y); void reconstruct(tree_node **root,tree_node *x); int normal_insert(tree_node **root,tree_node *x,int f); int insert(tree_node **root,tree_node *x,int f); void delete(tree_node **root,tree_node *head,int data); int t[100000],x[100000],y[100000],u[100000],q1[100000],q2[100000],q3[100000],ans[100000],g[100000],s[100000],s2[100000],s3[100000],qf[100000]; tree_node *color[100000],*head[100000],*query[100000]; int main(){ int n,m,q,g1,g2,g3,g4,temp,temp2,temp3,i; tree_node *p,*p2,**p3,*p4,*nxt; scanf("%d%d%d",&n,&m,&q); for(i=0;i<n;i++) scanf("%d",t+i); for(i=0;i<m;i++){ scanf("%d%d%d",x+i,y+i,u+i); x[i]--; y[i]--; } for(i=0;i<q;i++){ scanf("%d%d%d",q1+i,q2+i,q3+i); q1[i]--; q2[i]--; ans[i]=-1; } sort_a3(u,x,y,m); for(i=0;i<n;i++){ g[i]=i; p=(tree_node*)malloc(sizeof(tree_node)); p->data=t[i]; p->left=p->right=p->parent=NULL; insert(color+i,p,0); s[i]=1; } for(i=0;i<q;i++) if(q1[i]==q2[i]){ p=(tree_node*)malloc(sizeof(tree_node)); p->data=q3[i]; p->idx=i; p->left=p->right=p->parent=NULL; insert(&query[q1[i]],p,0); s3[q1[i]]++; } else{ p=(tree_node*)malloc(sizeof(tree_node)); p->data=q3[i]; p->idx=i; p->left=head[q1[i]]; head[q1[i]]=p; s2[q1[i]]++; p=(tree_node*)malloc(sizeof(tree_node)); p->data=q3[i]; p->idx=i; p->left=head[q2[i]]; head[q2[i]]=p; s2[q2[i]]++; } for(i=0;i<m;i++){ g1=get_group(x[i]); g2=get_group(y[i]); if(g1==g2) continue; if(s[g1]<s[g2]){ merge(color[g1],&color[g2],&s[g2],1); p=color[g2]; temp=s[g2]; } else{ merge(color[g2],&color[g1],&s[g1],1); p=color[g1]; temp=s[g1]; } if(s2[g1]<s2[g2]){ for(p2=head[g1];p2;p2=nxt){ nxt=p2->left; g3=get_group(q1[p2->idx]); g4=get_group(q2[p2->idx]); if(!qf[p2->idx]){ if((g3==g1 && g4==g2) || (g3==g2 && g4==g1)){ qf[p2->idx]=1; p2->left=p2->right=p2->parent=NULL; insert(&query[g1],p2,0); s3[g1]++; } else{ p2->left=head[g2]; head[g2]=p2; s2[g2]++; } } } p2=head[g2]; temp2=s2[g2]; } else{ for(p2=head[g2];p2;p2=nxt){ nxt=p2->left; g3=get_group(q1[p2->idx]); g4=get_group(q2[p2->idx]); if(!qf[p2->idx]){ if((g3==g1 && g4==g2) || (g3==g2 && g4==g1)){ qf[p2->idx]=1; p2->left=p2->right=p2->parent=NULL; insert(&query[g2],p2,0); s3[g2]++; } else{ p2->left=head[g1]; head[g1]=p2; s2[g1]++; } } } p2=head[g1]; temp2=s2[g1]; } if(s3[g1]<s3[g2]){ merge(query[g1],&query[g2],&s3[g2],0); p3=&query[g2]; temp3=s3[g2]; } else{ merge(query[g2],&query[g1],&s3[g1],0); p3=&query[g1]; temp3=s3[g1]; } while(1){ if(!temp3) break; p4=get_min(*p3); if(p4->data>temp) break; ans[p4->idx]=u[i]; delete(p3,*p3,p4->data); temp3--; } update_group(x[i],g1); update_group(y[i],g1); s[g1]=temp; s2[g1]=temp2; s3[g1]=temp3; color[g1]=p; head[g1]=p2; query[g1]=*p3; } for(i=0;i<q;i++){ if(q1[i]==q2[i] && q3[i]==1) ans[i]=0; printf("%d\n",ans[i]); } return 0; } tree_node *get_min(tree_node *root){ if(!root) return NULL; if(root->left) return get_min(root->left); return root; } void merge(tree_node *root,tree_node **m,int *s,int f){ if(!root) return; merge(root->left,m,s,f); merge(root->right,m,s,f); root->left=root->right=root->parent=NULL; (*s)+=insert(m,root,f); return; } int get_group(int x){ while(g[x]!=x) x=g[x]; return x; } void update_group(int x,int y){ int z=-1; while(1){ if(x==z) break; z=x; x=g[x]; g[z]=y; } return; } void sort_a3(int*a,int*b,int*c,int size){ if (size < 2) return; int m = (size+1)/2,i; int *left_a,*left_b,*left_c,*right_a,*right_b,*right_c; left_a=(int*)malloc(m*sizeof(int)); right_a=(int*)malloc((size-m)*sizeof(int)); left_b=(int*)malloc(m*sizeof(int)); right_b=(int*)malloc((size-m)*sizeof(int)); left_c=(int*)malloc(m*sizeof(int)); right_c=(int*)malloc((size-m)*sizeof(int)); for(i=0;i<m;i++){ left_a[i]=a[i]; left_b[i]=b[i]; left_c[i]=c[i]; } for(i=0;i<size-m;i++){ right_a[i]=a[i+m]; right_b[i]=b[i+m]; right_c[i]=c[i+m]; } sort_a3(left_a,left_b,left_c,m); sort_a3(right_a,right_b,right_c,size-m); merge3(a,left_a,right_a,b,left_b,right_b,c,left_c,right_c,m,size-m); free(left_a); free(right_a); free(left_b); free(right_b); free(left_c); free(right_c); return; } void merge3(int*a,int*left_a,int*right_a,int*b,int*left_b,int*right_b,int*c,int*left_c,int*right_c,int left_size,int right_size){ int i = 0, j = 0; while (i < left_size|| j < right_size) { if (i == left_size) { a[i+j] = right_a[j]; b[i+j] = right_b[j]; c[i+j] = right_c[j]; j++; } else if (j == right_size) { a[i+j] = left_a[i]; b[i+j] = left_b[i]; c[i+j] = left_c[i]; i++; } else if (left_a[i] <= right_a[j]) { a[i+j] = left_a[i]; b[i+j] = left_b[i]; c[i+j] = left_c[i]; i++; } else { a[i+j] = right_a[j]; b[i+j] = right_b[j]; c[i+j] = right_c[j]; j++; } } return; } void left_rotate(tree_node **root,tree_node *x){ tree_node *y; y=x->right; if(!y) return; x->right=y->left; if(y->left) y->left->parent=x; y->parent=x->parent; if(x->parent==NULL) *root=y; else if(x==x->parent->left) x->parent->left=y; else x->parent->right=y; y->left=x; x->parent=y; return; } void right_rotate(tree_node **root,tree_node *y){ tree_node *x; x=y->left; if(!x) return; y->left=x->right; if(x->right) x->right->parent=y; x->parent=y->parent; if(y->parent==NULL) *root=x; else if(y==y->parent->right) y->parent->right=x; else y->parent->left=x; x->right=y; y->parent=x; return; } void reconstruct(tree_node **root,tree_node *x){ tree_node *y,*z; y=x->parent; z=x->parent->parent; x->colour=black; z->colour=red; x->parent=z->parent; if(z->parent==NULL) *root=x; else if(z==z->parent->left) z->parent->left=x; else z->parent->right=x; if(z->left==y){ x->left=y; x->right=z; } else{ x->left=z; x->right=y; } y->parent=z->parent=x; y->left=y->right=z->left=z->right=NULL; return; } int normal_insert(tree_node **root,tree_node *x,int f){ if(*root==NULL) *root=x; else if(f && (*root)->data==x->data) return 0; else{ x->parent=*root; if((*root)->data>x->data) return normal_insert(&((*root)->left),x,f); else return normal_insert(&((*root)->right),x,f); } return 1; } int insert(tree_node **root,tree_node *x,int f){ if(!normal_insert(root,x,f)) return 0; tree_node *y; x->colour=red; while(x!=*root && x->parent->colour==red){ if(x->parent==x->parent->parent->left){ y=x->parent->parent->right; if(!y) if(x==x->parent->left){ x->parent->colour=black; x->parent->parent->colour=red; right_rotate(root,x->parent->parent); } else{ y=x->parent; reconstruct(root,x); x=y; } else if(y->colour==red){ x->parent->colour=black; y->colour=black; x->parent->parent->colour=red; x=x->parent->parent; } else{ if(x==x->parent->right){ x=x->parent; left_rotate(root,x); } x->parent->colour=black; x->parent->parent->colour=red; right_rotate(root,x->parent->parent); } } else{ y=x->parent->parent->left; if(!y) if(x==x->parent->right){ x->parent->colour=black; x->parent->parent->colour=red; left_rotate(root,x->parent->parent); } else{ y=x->parent; reconstruct(root,x); x=y; } else if(y->colour==red){ x->parent->colour=black; y->colour=black; x->parent->parent->colour=red; x=x->parent->parent; } else{ if(x==x->parent->left){ x=x->parent; right_rotate(root,x); } x->parent->colour=black; x->parent->parent->colour=red; left_rotate(root,x->parent->parent); } } } (*root)->colour=black; return 1; } void delete(tree_node **root,tree_node *head,int data){ tree_node *db,*parent,*brother,*child,none; if(!head) return; if(data<head->data || (data==head->data && head->left)){ delete(root,head->left,data); return; } if(data>head->data){ delete(root,head->right,data); return; } if(data==head->data){ if(head->left && head->right){ db=head->right; while(db->left) db=db->left; head->data=db->data; // Do node copy here. head->idx=db->idx; head=db; } if(head->left==NULL && head->right==NULL){ parent=head->parent; if(!parent){ *root=NULL; free(head); return; } brother=(parent->left==head)?parent->right:parent->left; if(head->colour==red){ if(parent->left==head) parent->left=NULL; else parent->right=NULL; free(head); return; } if(parent->left==head) parent->left=&none; else parent->right=&none; none.parent=parent; none.colour=black; db=&none; free(head); } else{ parent=head->parent; child=(!head->left)?head->right:head->left; if(!parent){ *root=child; child->parent=NULL; child->colour=black; free(head); return; } if(parent->left==head) parent->left=child; else parent->right=child; child->parent=parent; db=child; free(head); } } while(db){ if(db->colour==red){ db->colour=black; return; } if(db==*root) return; parent=db->parent; brother=(parent->left==db)?parent->right:parent->left; if(!brother) db=parent; else if(brother==parent->right){ if(brother->colour==black && brother->right && brother->right->colour==red){ brother->colour=parent->colour; brother->right->colour=black; parent->colour=black; left_rotate(root,parent); if(db==&none) parent->left=NULL; return; } else if(brother->colour==black && brother->left && brother->left->colour==red){ brother->left->colour=parent->colour; parent->colour=black; right_rotate(root,brother); left_rotate(root,parent); if(db==&none) parent->left=NULL; return; } else if(brother->colour==black){ brother->colour=red; if(db==&none) parent->left=NULL; db=parent; } else{ brother->colour=black; parent->colour=red; left_rotate(root,parent); } } else{ if(brother->colour==black && brother->left && brother->left->colour==red){ brother->colour=parent->colour; brother->left->colour=black; parent->colour=black; right_rotate(root,parent); if(db==&none) parent->right=NULL; return; } else if(brother->colour==black && brother->right && brother->right->colour==red){ brother->right->colour=parent->colour; parent->colour=black; left_rotate(root,brother); right_rotate(root,parent); if(db==&none) parent->right=NULL; return; } else if(brother->colour==black){ brother->colour=red; if(db==&none) parent->right=NULL; db=parent; } else{ brother->colour=black; parent->colour=red; right_rotate(root,parent); } } } return; } Travel in HackerLand C++ Solution #include <ios> #include <iostream> #include <queue> #include <map> #include <set> #include <algorithm> struct st { std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int> >, std::greater<std::pair<int, int> > > pq; //priority queue contains (DISTINCT CITIES REQUIRED, query#) sorted by smallest cities required first std::map<int, int> c; //(query#, cities found) when it becomes 2, we add it to the pq std::set<int> ds; //distinct types }; int par[100005] = {}; int siz[100005] = {}; int req[100005] = {}; int ans[100005] = {}; //store the answers here std::vector<std::pair<int, std::pair<int, int> > > quers; // weight, a, b std::vector<st> vec; void merge_and_check(int a, int b, int w) //merge b to a { for (std::set<int>::iterator it = vec[b].ds.begin(); it != vec[b].ds.end(); it++) vec[a].ds.insert(*it); while (!vec[b].pq.empty()) { vec[a].pq.push(vec[b].pq.top()); vec[b].pq.pop(); } for (std::map<int, int>::iterator it = vec[b].c.begin(); it != vec[b].c.end(); it++) { if (vec[a].c.find(it->first) == vec[a].c.end()) vec[a].c.insert(std::make_pair(it->first, it->second)); else { vec[a].c[it->first]++; if (vec[a].c[it->first] == 2) vec[a].pq.push(std::make_pair(req[it->first], it->first)); } } vec[b].ds.clear(); vec[b].c.clear(); while (!vec[a].pq.empty() && vec[a].pq.top().first <= vec[a].ds.size()) { ans[vec[a].pq.top().second] = w; vec[a].pq.pop(); } } int fnd(int a) { int x = par[a]; while (x != par[x]) x = par[x]; return x; } void join(int a, int b, int w) { a = fnd(a); b = fnd(b); if (a != b) { //time to merge if (siz[a] > siz[b]) { siz[a] += siz[b]; par[b] = a; merge_and_check(a, b, w); } else if (siz[a] < siz[b]) { siz[b] += siz[a]; par[a] = b; merge_and_check(b, a, w); } else { siz[a] += siz[b]; par[b] = a; merge_and_check(a, b, w); } } } int main() { for (int i = 0; i < 100005; i++) { par[i] = i; siz[i] = 1; ans[i] = -1; } int n, m, q, a, b, w, x, y; std::cin >> n >> m >> q; for (int i = 0; i < n; i++) vec.push_back(st()); for (int i = 0; i < n; i++) { std::cin >> x; vec[i].ds.insert(x); } for (int i = 0; i < m; i++) { std::cin >> a >> b >> w; a--; b--; quers.push_back(std::make_pair(w, std::make_pair(a, b))); } for (int i = 0; i < q; i++) { std::cin >> x >> y >> req[i]; x--; y--; if (x == y) { if (req[i] == 1) ans[i] = 0; else { vec[x].c.insert(std::make_pair(i, 2)); vec[x].pq.push(std::make_pair(req[i], i)); } } else { vec[x].c.insert(std::make_pair(i, 1)); vec[y].c.insert(std::make_pair(i, 1)); } } std::sort(quers.begin(), quers.end()); for (std::vector<std::pair<int, std::pair<int, int> > >::iterator it = quers.begin(); it != quers.end(); it++) { join(it->second.first, it->second.second, it->first); } for (int i = 0; i < q; i++) std::cout << ans[i] << '\n'; } Travel in HackerLand C Sharp Solution using System; using System.Linq; using System.Text; using System.IO; using System.Diagnostics; using System.Globalization; using System.Collections.Generic; using System.Threading; using kp.Algo; using kp.Algo.IO; using kp.Algo.DataStructures; namespace CodeForces { internal class Solution { const int StackSize = 20 * 1024 * 1024; private void Solve() { int n = NextInt(); int m = NextInt(); int q = NextInt(); var t = NextIntArray(n); int[] ans = new int[q]; for (int i = 0; i < q; i++) { ans[i] = -1; } var dsu = new DisjointSetUnion(n); var pq = new PriorityQueue<Pair<int, int>>[n]; var hs = new HashSet<int>[n]; var open = new Dictionary<int, List<int>>[n]; for (int i = 0; i < n; i++) { pq[i] = new PriorityQueue<Pair<int, int>>(); hs[i] = new HashSet<int>(); hs[i].Add(t[i]); open[i] = new Dictionary<int, List<int>>(); } var edges = new List<Tuple<int, int, int>>(); for (int i = 0; i < m; i++) { var x = NextInt() - 1; var y = NextInt() - 1; var u = NextInt(); edges.Add(new Tuple<int, int, int>(u, x, y)); } int[] qx = new int[q]; int[] qy = new int[q]; int[] qk = new int[q]; for (int i = 0; i < q; i++) { qx[i] = NextInt() - 1; qy[i] = NextInt() - 1; qk[i] = NextInt(); if (qx[i] != qy[i]) { if (!open[qx[i]].ContainsKey(qy[i])) { open[qx[i]].Add(qy[i], new List<int>()); } open[qx[i]][qy[i]].Add(i); if (!open[qy[i]].ContainsKey(qx[i])) { open[qy[i]].Add(qx[i], new List<int>()); } open[qy[i]][qx[i]].Add(i); } else { if (qk[i] == 1) { ans[i] = 0; } else { pq[qx[i]].Add(new Pair<int, int> { First = qk[i], Second = i }); } } } edges.Sort(); for (int i = 0; i < edges.Count; ++i) { var x = edges[i].Item2; var y = edges[i].Item3; var px = dsu.GetRepresentative(x); var py = dsu.GetRepresentative(y); if (px == py) { continue; } dsu.Join(x, y); var p = dsu.GetRepresentative(x); if (hs[px].Count < hs[py].Count) { foreach (var e in hs[px]) { hs[py].Add(e); } hs[p] = hs[py]; } else { foreach (var e in hs[py]) { hs[px].Add(e); } hs[p] = hs[px]; } if (open[px].Count < open[py].Count) { foreach (var kvp in open[px]) { if (dsu.GetRepresentative(kvp.Key) == p) { foreach (var vv in kvp.Value) { pq[p].Add(new Pair<int, int> { First = qk[vv], Second = vv }); } } else { if (!open[py].ContainsKey(kvp.Key)) { open[py].Add(kvp.Key, new List<int>()); } open[py][kvp.Key].AddRange(kvp.Value); } } open[p] = open[py]; } else { foreach (var kvp in open[py]) { if (dsu.GetRepresentative(kvp.Key) == p) { foreach (var vv in kvp.Value) { pq[p].Add(new Pair<int, int> { First = qk[vv], Second = vv }); } } else { if (!open[px].ContainsKey(kvp.Key)) { open[px].Add(kvp.Key, new List<int>()); } open[px][kvp.Key].AddRange(kvp.Value); } } open[p] = open[px]; } if (pq[px].Size < pq[py].Size) { var pqx = pq[px].ToArray(); for (int j = 1; j <= pq[px].Size; ++j) { pq[py].Add(pqx[j]); } pq[p] = pq[py]; } else { var pqy = pq[py].ToArray(); for (int j = 1; j <= pq[py].Size; ++j) { pq[px].Add(pqy[j]); } pq[p] = pq[px]; } while (pq[p].Size > 0 && pq[p].PeekMin().First <= hs[p].Count) { if (ans[pq[p].PeekMin().Second] == -1) ans[pq[p].PeekMin().Second] = edges[i].Item1; pq[p].RemoveMin(); } } for (int i = 0; i < q; i++) { Out.WriteLine(ans[i]); } } #region Local wireup public int[] NextIntArray(int size) { var res = new int[size]; for (int i = 0; i < size; ++i) res[i] = NextInt(); return res; } public long[] NextLongArray(int size) { var res = new long[size]; for (int i = 0; i < size; ++i) res[i] = NextLong(); return res; } public double[] NextDoubleArray(int size) { var res = new double[size]; for (int i = 0; i < size; ++i) res[i] = NextDouble(); return res; } public int NextInt() { return _in.NextInt(); } public long NextLong() { return _in.NextLong(); } public string NextLine() { return _in.NextLine(); } public double NextDouble() { return _in.NextDouble(); } Scanner _in; static readonly TextWriter Out = Console.Out; void Start() { #if KP_HOME _in = new Scanner("input.txt"); var timer = new Stopwatch(); timer.Start(); #else _in = new Scanner( Console.In, false ); #endif var t = new Thread(Solve, StackSize); t.Start(); t.Join(); #if KP_HOME timer.Stop(); Console.WriteLine(string.Format(CultureInfo.InvariantCulture, "Done in {0} seconds.\nPress <Enter> to exit.", timer.ElapsedMilliseconds / 1000.0)); Console.ReadLine(); #endif } static void Main() { new Solution().Start(); } #endregion } } namespace kp.Algo { } namespace kp.Algo.DataStructures { public class DisjointSetUnion { private readonly int[] _p; private readonly int[] _r; /// <summary> /// Creates DSU structure. /// Sets are numbered from 0 to n-1. /// </summary> public DisjointSetUnion(int n) { _p = new int[n]; _r = new int[n]; for (int i = 0; i < n; i++) { _p[i] = i; } } /// <summary> /// Checks whether a and b are in one set /// </summary> public bool InOneSet(int a, int b) { return GetP(a) == GetP(b); } /// <summary> /// Gets representative of a set to which <paramref name="a"/> belongs. /// </summary> /// <param name="a">Element</param> /// <returns></returns> public int GetRepresentative(int a) { return GetP(a); } /// <summary> /// Joins sets which a and b belong to /// If they are already in one set, then nothing happens and method returns False /// </summary> /// <returns>True, if a and b were in different sets, False otherwise</returns> public bool Join(int a, int b) { int pa = GetP(a), pb = GetP(b); if (pa == pb) return false; if (_r[pa] > _r[pb]) { _p[pb] = pa; } else { if (_r[pa] == _r[pb]) ++_r[pb]; _p[pa] = pb; } return true; } private int GetP(int a) { if (_p[a] == a) return a; return _p[a] = GetP(_p[a]); } } public class PriorityQueue<T> where T : IComparable<T> { private T[] _data; public int Size { get; private set; } public PriorityQueue() : this(4) { } public PriorityQueue(int maxSize) { _data = new T[maxSize + 1]; } public void Add(T elem) { if (Size + 1 == _data.Length) { EnsureSize(Size + 1); } _data[++Size] = elem; Up(Size); } /// <summary> /// Removes the smallest element /// </summary> public T RemoveMin() { if (Size == 0) throw new InvalidOperationException("Queue underflow"); T res = _data[1]; _data[1] = _data[Size--]; Down(1); return res; } /// <summary> /// Gets array with all elements /// </summary> public T[] ToArray() { return _data; } public T PeekMin() { if (Size == 0) throw new InvalidOperationException("Queue underflow"); return _data[1]; } private void EnsureSize(int need) { var next = _data.Length; while (next < need + 1) next *= 2; T[] nextData = new T[next]; Array.Copy(_data, nextData, _data.Length); _data = nextData; } private void Down(int u) { int l = 2 * u, r = l + 1, m = u; if (l <= Size && _data[m].CompareTo(_data[l]) > 0) m = l; if (r <= Size && _data[m].CompareTo(_data[r]) > 0) m = r; if (m != u) { T tmp = _data[u]; _data[u] = _data[m]; _data[m] = tmp; Down(m); } } private void Up(int u) { if (u > 1) { int p = u / 2; if (_data[p].CompareTo(_data[u]) > 0) { T tmp = _data[u]; _data[u] = _data[p]; _data[p] = tmp; Up(p); } } } } public class Pair<T, K> : IComparable<Pair<T, K>> where T : IComparable<T> where K : IComparable<K> { public T First { get; set; } public K Second { get; set; } #region IComparable<Pair<T,K>> Members public int CompareTo( Pair<T, K> other ) { if ( First.CompareTo( other.First ) != 0 ) return First.CompareTo( other.First ); return Second.CompareTo( other.Second ); } #endregion } } namespace kp.Algo.IO { public class Scanner : IDisposable { #region Fields readonly System.IO.TextReader _reader; readonly int _bufferSize; readonly bool _closeReader; readonly char[] _buffer; int _length, _pos; #endregion #region .ctors public Scanner( System.IO.TextReader reader, int bufferSize, bool closeReader ) { _reader = reader; _bufferSize = bufferSize; _closeReader = closeReader; _buffer = new char[_bufferSize]; FillBuffer( false ); } public Scanner( System.IO.TextReader reader, bool closeReader ) : this( reader, 1 << 16, closeReader ) { } public Scanner( string fileName ) : this( new System.IO.StreamReader( fileName, System.Text.Encoding.Default ), true ) { } #endregion #region IDisposable Members public void Dispose() { if ( _closeReader ) { _reader.Close(); } } #endregion #region Properties public bool Eof { get { if ( _pos < _length ) return false; FillBuffer( false ); return _pos >= _length; } } #endregion #region Methods private char NextChar() { if ( _pos < _length ) return _buffer[_pos++]; FillBuffer( true ); return _buffer[_pos++]; } private char PeekNextChar() { if ( _pos < _length ) return _buffer[_pos]; FillBuffer( true ); return _buffer[_pos]; } private void FillBuffer( bool throwOnEof ) { _length = _reader.Read( _buffer, 0, _bufferSize ); if ( throwOnEof && Eof ) { throw new System.IO.IOException( "Can't read beyond the end of file" ); } _pos = 0; } public int NextInt() { var neg = false; int res = 0; SkipWhitespaces(); if ( !Eof && PeekNextChar() == '-' ) { neg = true; _pos++; } while ( !Eof && !IsWhitespace( PeekNextChar() ) ) { var c = NextChar(); if ( c < '0' || c > '9' ) throw new ArgumentException( "Illegal character" ); res = 10 * res + c - '0'; } return neg ? -res : res; } public int[] NextIntArray( int n ) { var res = new int[n]; for ( int i = 0; i < n; i++ ) { res[i] = NextInt(); } return res; } public long NextLong() { var neg = false; long res = 0; SkipWhitespaces(); if ( !Eof && PeekNextChar() == '-' ) { neg = true; _pos++; } while ( !Eof && !IsWhitespace( PeekNextChar() ) ) { var c = NextChar(); if ( c < '0' || c > '9' ) throw new ArgumentException( "Illegal character" ); res = 10 * res + c - '0'; } return neg ? -res : res; } public long[] NextLongArray( int n ) { var res = new long[n]; for ( int i = 0; i < n; i++ ) { res[i] = NextLong(); } return res; } public string NextLine() { SkipUntilNextLine(); if ( Eof ) return ""; var builder = new System.Text.StringBuilder(); while ( !Eof && !IsEndOfLine( PeekNextChar() ) ) { builder.Append( NextChar() ); } return builder.ToString(); } public double NextDouble() { SkipWhitespaces(); var builder = new System.Text.StringBuilder(); while ( !Eof && !IsWhitespace( PeekNextChar() ) ) { builder.Append( NextChar() ); } return double.Parse( builder.ToString(), System.Globalization.CultureInfo.InvariantCulture ); } public double[] NextDoubleArray( int n ) { var res = new double[n]; for ( int i = 0; i < n; i++ ) { res[i] = NextDouble(); } return res; } public string NextToken() { SkipWhitespaces(); var builder = new System.Text.StringBuilder(); while ( !Eof && !IsWhitespace( PeekNextChar() ) ) { builder.Append( NextChar() ); } return builder.ToString(); } private void SkipWhitespaces() { while ( !Eof && IsWhitespace( PeekNextChar() ) ) { ++_pos; } } private void SkipUntilNextLine() { while ( !Eof && IsEndOfLine( PeekNextChar() ) ) { ++_pos; } } private static bool IsWhitespace( char c ) { return c == ' ' || c == '\t' || c == '\n' || c == '\r'; } private static bool IsEndOfLine( char c ) { return c == '\n' || c == '\r'; } #endregion } } Travel in HackerLand Java Solution import java.io.*; import java.util.*; public class Solution { static TreeSet<Integer>[] all; static int ind; static void swapAll(int root_A, int root_B) { TreeSet<Integer> tmp = all[root_A]; all[root_A] = all[root_B]; all[root_B] = tmp; } static class DisjointUnionSets { int[] parent; int[] rank; public DisjointUnionSets(int n) { parent = new int[n]; rank = new int[n]; } int findset(int x) { return x == parent[x] ? x : findset(parent[x]); } void union(int x, int y) { int xRoot = findset(x); int yRoot = findset(y); if (xRoot == yRoot) { return; } if (rank[xRoot] < rank[yRoot]) { parent[xRoot] = parent[yRoot]; rank[yRoot] += rank[xRoot]; if (all[xRoot].size() > all[yRoot].size()) { swapAll(xRoot, yRoot); } while (all[xRoot].size() > 0) { int tmp = all[xRoot].pollFirst(); all[yRoot].add(tmp); } } else { parent[yRoot] = parent[xRoot]; rank[xRoot] += rank[yRoot]; if (all[xRoot].size() < all[yRoot].size()) { swapAll(xRoot, yRoot); } while (all[yRoot].size() > 0) { int tmp = all[yRoot].pollFirst(); all[xRoot].add(tmp); } } } } static class QS { int x, y, k, id; public QS(int x, int y, int k, int id) { this.x = x; this.y = y; this.k = k; this.id = id; } } static class Edge { int u; int v; public Edge(int xx, int yy) { this.u = xx; this.v = yy; } } static class EdgeW { int w; Edge edge; public EdgeW(int xx, Edge yy) { this.w = xx; this.edge = yy; } } static EdgeW[] edges; static void apply(DisjointUnionSets dus, int k) { while (ind < edges.length) { if (edges[ind].w > k) { break; } else { dus.union(edges[ind].edge.u, edges[ind].edge.v); ind++; } } } @SuppressWarnings("unchecked") public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH"))); StringTokenizer st = new StringTokenizer(br.readLine()); int n = Integer.parseInt(st.nextToken()); int m = Integer.parseInt(st.nextToken()); int q = Integer.parseInt(st.nextToken()); Map<Integer, Integer> map = new HashMap<>(); int cntb = 0; int[] revmp1 = new int[n + 1]; st = new StringTokenizer(br.readLine()); for (int i = 1; i <= n; i++) { int item = Integer.parseInt(st.nextToken()); if (!map.containsKey(item)) { map.put(item, ++cntb); } revmp1[i] = map.get(item); } edges = new EdgeW[m]; for (int i = 0; i < m; i++) { st = new StringTokenizer(br.readLine()); int u = Integer.parseInt(st.nextToken()); int v = Integer.parseInt(st.nextToken()); int w = Integer.parseInt(st.nextToken()); edges[i] = new EdgeW(w, new Edge(u, v)); } Arrays.sort(edges, (a, b) -> a.w - b.w); int[] revmp2 = new int[m+1]; int cnte = 0; map.clear(); for (int k = 0; k < edges.length; k++) { EdgeW i = edges[k]; if (!map.containsKey(i.w)) { map.put(i.w, ++cnte); revmp2[cnte] = i.w; } edges[k].w = map.get(i.w); } int tot = 0; int[] ans = new int[q]; QS[] qs = new QS[q+1]; for (int i = 0; i < q; i++) { st = new StringTokenizer(br.readLine()); int u = Integer.parseInt(st.nextToken()); int v = Integer.parseInt(st.nextToken()); int w = Integer.parseInt(st.nextToken()); if (w > cntb) { ans[i] = -1; } else { tot++; qs[tot] = new QS(u, v, w, i); } } int[] lo = new int[tot + 1]; int[] hi = new int[tot + 1]; for (int i = 1; i <= tot; i++) { lo[i] = 1; hi[i] = cnte + 1; } Stack<Integer>[] check = new Stack[Math.max(n + 1, m)]; all = new TreeSet[n + 1]; for (int i = 0; i <= n; i++) { all[i] = new TreeSet<>(); } for (int i = 0; i < check.length; i++) { check[i] = new Stack<>(); } DisjointUnionSets dus = new DisjointUnionSets(n + 1); boolean changed = true; while (changed) { changed = false; for (int i = 0; i <= n; i++) { all[i].clear(); all[i].add(revmp1[i]); dus.parent[i] = i; dus.rank[i] = 1; } int upto = 0; for (int i = 1; i <= tot; i++) { if (lo[i] != hi[i]) { check[(lo[i] + hi[i]) >> 1].add(i); upto = Math.max(upto, (lo[i] + hi[i]) >> 1); } } ind = 0; for (int i = 1; i <= upto; i++) { apply(dus, i); while (check[i].size() > 0) { changed = true; int id = check[i].pop(); int rootx = dus.findset(qs[id].x); int rooty = dus.findset(qs[id].y); if (rootx != rooty) { lo[id] = i + 1; } else { if (all[rootx].size() >= qs[id].k) { hi[id] = i; } else { lo[id] = i + 1; } } } } } for (int i = 1; i <= tot; i++) { if (lo[i] <= cnte) { ans[qs[i].id] = revmp2[lo[i]]; } else { ans[qs[i].id] = -1; } } for (int i = 0; i < q; i++) { bw.write(ans[i] + "\n"); } bw.newLine(); bw.close(); br.close(); } } Travel in HackerLand Python Solution from collections import defaultdict import heapq def root(ids, i): while ids[i] != i: ids[i] = ids[ids[i]] i = ids[i] return i def union(queries, blds, ids, p, q): i = root(ids, p) j = root(ids, q) if i == j: return i, j if len(blds[i]) > len(blds[j]): bigb, smb = blds[i], blds[j] else: bigb, smb = blds[j], blds[i] for b in smb: bigb.add(b) del smb if len(queries[i][0]) + len(queries[i][1]) > len(queries[j][0]) + len(queries[j][1]): ids[j] = i blds[i] = bigb blds[j] = None return j, i else: ids[i] = j blds[j] = bigb blds[i] = None return i, j n, m, q = map(int, input().split()) T = list(map(int, input().split())) edges = [] for i in range(m): x, y, u = map(int, input().split()) edges.append((u, x-1, y-1)) edges.sort() queries = [[set([]), []] for _ in range(n)] res = [-1 for i in range(q)] for qi in range(q): x, y, k = map(int, input().split()) x, y = sorted([x-1, y-1]) if x == y and k <= 1: res[qi] = 0 else: qr = (k, x, y, qi) if x == y: heapq.heappush(queries[x][1], qr) else: queries[x][0].add(qr) queries[y][0].add(qr) ids = [i for i in range(n)] blds = [set([T[i]]) for i in range(n)] for u, x, y in edges: i, j = union(queries, blds, ids, x, y) if i == j: continue tot_blds = len(blds[j]) #print u, x, y, i, j, queries[i], queries[j], tot_blds for qr in queries[i][0]: if root(ids, qr[1]) != root(ids, qr[2]): queries[j][0].add(qr) else: queries[j][0].discard(qr) if tot_blds >= qr[0]: res[qr[-1]] = u else: heapq.heappush(queries[j][1], qr) while queries[i][1] and queries[i][1][0][0] <= tot_blds: res[queries[i][1][0][-1]] = u heapq.heappop(queries[i][1]) for qr in queries[i][1]: heapq.heappush(queries[j][1], qr) queries[i][0] = None queries[i][1] = None while queries[j][1] and queries[j][1][0][0] <= tot_blds: res[queries[j][1][0][-1]] = u heapq.heappop(queries[j][1]) for r in res: print(r) c C# C++ HackerRank Solutions java javascript python CcppCSharpHackerrank Solutionsjavajavascriptpython