In this HackerRank Travel in HackerLand problem solution, You will be given q queries. Each query takes the form of 3 space-separated integers, x, y, and k, denoting the respective values for starting city, destination city, and a 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 x and y that has at least k different buildings along the route. If there is no such path, print -1.

HackerRank Travel in HackerLand problem solution


Problem solution in Python.

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)
    

{"mode":"full","isActive":false}


Problem solution in Java.

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();
  }
}

{"mode":"full","isActive":false}


Problem solution in C++.

#include <set>
#include <cmath>
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

#define sz2 200001
#define ii pair<int, int>
#define pb push_back
#define mp make_pair
#define ff first
#define ss second

int qq, N, M, Q, K, C, max_edge = 1000000001;

vector<ii > G[100001];
vector<pair<int, ii > > E;
priority_queue<pair<int, ii > > pq;
pair <int, ii > q[2000001];
int lvl[sz2],T[100001],a[1000001],L[sz2],
    R[sz2],p[sz2],parent[sz2][20],col[100001],
    ll[sz2],rr[sz2],weight[sz2],dis[sz2],
    ans[2000001],st[5000005],used[10000001];
    
bool vis[100001];

int mycmp(pair <int, ii > a, pair <int, ii > b)
{
    if (a.ss.ff != b.ss.ff) return a.ss.ff < b.ss.ff;
    return a.ff < b.ff;
}

// DisjointSet
int find_parent(int i) {
	if (p[i] == i) return i;
	return p[i] = find_parent(p[i]);
}

void set_lvl(int v, int l) {
	lvl[v] = l;
	if (v > N) {
		set_lvl(ll[v], l + 1);
		set_lvl(rr[v], l + 1);
	}
}

// LeastCommonAncestor

void build_lca() {
	for (int i = 1; i < 20; i++)
		for (int v = 1; v <= K; v++) {
			parent[v][i] = parent[parent[v][i - 1]][i - 1];
		}
}

int LCA(int u, int v) {
	if (lvl[u] > lvl[v]) swap(u, v);
	for (int i = 20; i > 0; i--)
		if (lvl[parent[v][i-1]] >= lvl[u]) v = parent[v][i-1];
	
	if (u == v) return u;
	
	for (int i = 20; i > 0; i--)
		if (parent[u][i-1] != parent[v][i-1]) {
			u = parent[u][i-1]; v = parent[v][i-1];
		}
		
	return parent[u][0];
}

class STO {
	public:
		
		int n, m;
		
		STO() { n = m = 0; }
		void add_color(int x) { a[++n] = x; }		
		void add_query(pair<int, ii > query) { q[++m] = query; }
		
		void solve() {
			sort(q + 1, q + m + 1, mycmp);
		    for (int i=1,j=1; i<=m; i++)
		    {
		        while(j <= q[i].ss.ff)
		        {
		            if (!used[a[j]]) {
		                Update(1, 1, n, j, 1);
		                used[a[j]] = j;
		            } else {
		                Update(1, 1, n, used[a[j]], 0);
		                Update(1, 1, n, j, 1);
		                used[a[j]] = j;
		            }
		            j++;
		        }
		        ans[q[i].ss.ss] = Find(1, 1, n, q[i].ff, q[i].ss.ff);
		    }
		}		
		int get_ans(int i) {
			return ans[i];
		}
		int Find(int ind, int A, int B, int l, int r)
		{
		    if (l > B || r < A) return 0;
		    if (A == l && B == r) return st[ind];
		    int mid = (A + B) / 2;
		    return Find(ind * 2, A, mid, l, min(mid, r)) + Find(ind * 2 + 1, mid + 1, B, max(mid + 1, l), r);
		}		
		void Update(int ind, int l, int r, int x, int d)
		{
		    if (l == r) st[ind] = d;
		    else {		    
        	    int mid = (l + r) / 2;
    		    if (x <= mid) Update(ind * 2, l, mid, x, d);
    		    else Update(ind * 2 + 1, mid + 1, r, x, d);   
    		    st[ind] = st[ind * 2] + st[ind * 2 + 1];
            }
		}		
};


STO seg_tree;


void dfs(int v) {
	if (v > N) {
		dfs(ll[v]);
		dfs(rr[v]);
		L[v] = L[ll[v]];
		R[v] = R[rr[v]];
		seg_tree.add_query(mp(L[v], mp(R[v], qq))); qq++;
	} else {
		C++;
		seg_tree.add_color(col[v]);
		L[v] = C;
		R[v] = C;
	}
}

void dfs1(int v) {
	if (v == 0) return;
	if (v > N) {
		dfs1(ll[v]);
		dfs1(rr[v]);
		weight[v] = seg_tree.get_ans(qq); qq++;
	} else weight[v] = 1;
	
}

void color_solve() {
	vector<int> v1, v2;
	for (int i = 1; i <= N; i++)
		v1.pb(T[i]);
	sort(v1.begin(), v1.end());
	v2.pb(v1[0]);
	
	for (int i = 1, sz = 0; i<v1.size(); i++)
		if (v2[sz - 1] != v1[i]) {
			v2.pb(v1[i]); sz++;
		}

	for (int i = 1; i <= N; i++)
		col[i] = lower_bound(v2.begin(), v2.end(), T[i]) - v2.begin() + 1;
}

int main() {
    int u, v, e, k, x, y;
    scanf("%d%d%d",&N,&M,&Q);
    for (int i = 1; i <= N; i++) {
        scanf("%d",&T[i]);
        G[0].pb(mp(i, -max_edge));
        G[i].pb(mp(0, -max_edge));
    }
    for (int j = 0; j < M; j++) {
        scanf("%d%d%d",&u,&v,&e);
        G[u].pb(mp(v, -e));
        G[v].pb(mp(u, -e));
    }
    
    pq.push(mp(0, mp(0, -1)));
	while (!pq.empty()) {
        e = pq.top().ff;
        x = pq.top().ss.ff;
        y = pq.top().ss.ss;
        pq.pop();
        
		if (!vis[x]) { 
            vis[x] = true;
            if (y != -1) E.pb(mp(-e, mp(x, y)));            
		    for (int i = 0; i < G[x].size(); i++)
              if (!vis[G[x][i].ff]) pq.push(mp(G[x][i].ss, mp(G[x][i].ff, x)));
        }
    }
    
    sort(E.begin(), E.end());
    for (int i = 0; i < 2 * N; i++)
    	p[i] = i;
    
    K = N;
    for (int i = 0; i < E.size(); i++) {
    	K++;
    	int X = find_parent(E[i].ss.ff), Y = find_parent(E[i].ss.ss);    	
    	p[X] = p[Y] = parent[X][0] = parent[Y][0] = K;    	
    	dis[K] = E[i].ff == max_edge?-1:E[i].ff;
    	ll[K] = X;
    	rr[K] = Y;
    }
    
    color_solve();    qq=1; dfs (K);
    seg_tree.solve(); qq=1; dfs1(K);

    set_lvl(K, 1);    
    lvl[0] = parent[0][0] = 0;
    build_lca();
    
    while (Q--) {
		scanf("%d%d%d",&x,&y,&k);
		if (weight[K] < k) {
			printf("-1\n");
			continue;
		}
		
		x = LCA(x, y);		
		if (weight[x] >= k) printf("%d\n",dis[x]);
		else {		
   		  for (int i = 19; i >= 0; i--) {
			 y = parent[x][i];
              if (y && weight[y] < k) x = y;
		  }		
		  printf("%d\n",dis[parent[x][0]]);
        }
	}
    
    return 0;
}

{"mode":"full","isActive":false}


Problem solution in C.

#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;
}

{"mode":"full","isActive":false}