Table of Contents
Travel in HackerLand – HackerRank Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
Solutions of Algorithms Data Structures Hard HackerRank:
Here are all the Solutions of Hard , Advanced , Expert Algorithms of Data Structure of Hacker Rank , Leave a comment for similar posts
C++ Travel in HackerLand HackerRank Solution
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<cassert>
#define PB push_back
#define MP make_pair
#define sz(v) (in((v).size()))
#define forn(i,n) for(in i=0;i<(n);++i)
#define forv(i,v) forn(i,sz(v))
#define fors(i,s) for(auto i=(s).begin();i!=(s).end();++i)
#define all(v) (v).begin(),(v).end()
using namespace std;
typedef long long in;
typedef vector<in> VI;
typedef vector<VI> VVI;
VI ans;
struct rsp{
in gl,gsz,id;
rsp(in a=0, in b=0, in c=0){
gl=a;
gsz=b;
id=c;
}
bool operator<(const rsp cp)const{
if(gl!=cp.gl)
return gl<cp.gl;
if(gsz!=cp.gsz)
return gsz<cp.gsz;
return id<cp.id;
}
};
struct onc{
in gsz,id;
onc(in a=0, in b=0){
gsz=a;
id=b;
}
bool operator<(const onc cp)const{
if(gsz!=cp.gsz)
return gsz<cp.gsz;
return id<cp.id;
}
};
in crsz;
struct unifnd{
VI ht,pr;
vector<set<onc> > oncs;
vector<set<rsp> > rsps;
vector<set<in> > blg,blgtyp;
in fnd(in a){
in ta=a;
while(a!=pr[a])a=pr[a];
in tt=ta;
while(ta!=a){
tt=pr[ta];
pr[ta]=a;
ta=tt;
}
return a;
}
void uni(in a, in b){
a=fnd(a);
b=fnd(b);
if(a==b)return;
if(ht[b]<ht[a])swap(a,b);
ht[b]+=ht[a];
pr[a]=b;
fors(i,blg[a]){
blg[b].insert(*i);
}
fors(i,blgtyp[a]){
blgtyp[b].insert(*i);
}
fors(i,rsps[a]){
if(blg[b].find(i->gl)!=blg[b].end()){
oncs[b].insert(onc(i->gsz,i->id));
}
else{
rsps[b].insert(*i);
}
}
auto it=oncs[b].begin();
for(auto i=oncs[b].begin();i!=oncs[b].end();){
if(i->gsz<=sz(blgtyp[b])){
if(ans[i->id]==-1)
ans[i->id]=crsz;
it=i;
++i;
oncs[b].erase(it);
continue;
}
break;
}
fors(i,oncs[a]){
if(ans[i->id]!=-1)
continue;
if(i->gsz<=sz(blgtyp[b])){
ans[i->id]=crsz;
}
else{
oncs[b].insert(*i);
}
}
}
void ini(in n){
ht.resize(n);
pr.resize(n);
blg.resize(n);
oncs.resize(n);
rsps.resize(n);
blgtyp.resize(n);
forn(i,n){
ht[i]=1;
pr[i]=i;
blg[i].insert(i);
}
}
};
unifnd tfd;
map<in,vector<pair<in,in> > > egs;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
in n,m,q;
cin>>n>>m>>q;
ans.resize(q,-1);
tfd.ini(n);
in ta,tb,tu;
crsz=0;
forn(z,n){
cin>>tu;
tfd.blgtyp[z].insert(tu);
}
forn(z,m){
cin>>ta>>tb>>tu;
--ta;
--tb;
egs[tu].PB(MP(ta,tb));
}
forn(z,q){
cin>>ta>>tb>>tu;
--ta;
--tb;
if(ta==tb){
if(tu==1){
ans[z]=0;
continue;
}
++tfd.ht[ta];
tfd.oncs[ta].insert(onc(tu,z));
continue;
}
++tfd.ht[ta];
++tfd.ht[tb];
tfd.rsps[ta].insert(rsp(tb,tu,z));
tfd.rsps[tb].insert(rsp(ta,tu,z));
}
fors(i,egs){
crsz=i->first;
forv(j,i->second){
tfd.uni(i->second[j].first,i->second[j].second);
}
}
forn(z,q){
cout<<ans[z]<<"\n";
}
return 0;
}
Java Travel in HackerLand HackerRank Solution
import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashSet;
import java.util.InputMismatchException;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Set;
public class G3 {
InputStream is;
PrintWriter out;
String INPUT = "";
void solve()
{
int n = ni(), m = ni(), Q = ni();
int[] types = na(n);
int[][] es = new int[m+Q][];
for(int i = 0;i < m;i++){
es[i] = new int[]{ni()-1, ni()-1, ni()};
}
Arrays.sort(es, 0, m, new Comparator<int[]>() {
public int compare(int[] a, int[] b) {
return a[2] - b[2];
}
});
int[] from = new int[n-1];
int[] to = new int[n-1];
int[] w = new int[n-1];
int p = 0;
DJSet ds = new DJSet(n);
for(int i = 0;i < m;i++){
if(!ds.union(es[i][0], es[i][1])){
from[p] = es[i][0];
to[p] = es[i][1];
w[p] = es[i][2];
p++;
}
}
int[][] qs = new int[Q][];
int[] ret = new int[Q];
for(int z = 0;z < Q;z++){
qs[z] = new int[]{ni()-1, ni()-1, ni()};
}
int[][][] g = packWU(n, from, to, w, p);
int[][] pars = parents3(g);
int[] par = pars[0], ord = pars[1], dep = pars[2], pw = pars[3];
int[][] spar = logstepParents(par);
int[][] smin = logstepArgmaxs(spar, pw);
int pp = m;
Arrays.fill(ret, -1);
for(int z = 0;z < Q;z++){
if(!ds.equiv(qs[z][0], qs[z][1])){
}else{
int lca = lca2(qs[z][0], qs[z][1], spar, dep);
int time = -1;
for(int i = qs[z][0];i != lca;){
int d = Integer.numberOfTrailingZeros(dep[i]-dep[lca]);
time = Math.max(time, pw[smin[d][i]]);
i = spar[d][i];
}
for(int i = qs[z][1];i != lca;){
int d = Integer.numberOfTrailingZeros(dep[i]-dep[lca]);
time = Math.max(time, pw[smin[d][i]]);
i = spar[d][i];
}
es[pp++] = new int[]{-1, qs[z][0], time, z, qs[z][2]};
}
}
Arrays.sort(es, 0, pp, new Comparator<int[]>() {
public int compare(int[] a, int[] b) {
if(a[2] != b[2])return a[2] - b[2];
return a.length - b.length;
}
});
DJSetX xds = new DJSetX(n);
for(int i = 0;i < n;i++){
Set<Integer> set = new HashSet<>();
set.add(types[i]);
xds.sets.set(i, set);
}
for(int i = 0;i < pp;i++){
if(es[i].length == 3){
xds.union(es[i][0], es[i][1]);
int r = xds.root(es[i][1]);
if(xds.pqs.get(r) != null){
while(!xds.pqs.get(r).isEmpty()){
if(xds.sets.get(r).size() >= xds.pqs.get(r).peek()[4]){
int[] e = xds.pqs.get(r).poll();
ret[e[3]] = es[i][2];
}else{
break;
}
}
}
}else{
int r = xds.root(es[i][1]);
// tr("new", xds.sets.get(r), es[i][4]);
if(xds.sets.get(r).size() >= es[i][4]){
ret[es[i][3]] = es[i][2];
}else{
if(xds.pqs.get(r) == null){
xds.pqs.set(r, new PriorityQueue<>(1, new Comparator<int[]>(){
public int compare(int[] a, int[] b){
return a[4] - b[4];
}
}));
}
xds.pqs.get(r).add(es[i]);
}
}
}
for(int v : ret){
out.println(v);
}
}
public static int[][] logstepArgmaxs(int[][] sp, int[] pw)
{
int m = sp.length;
int n = sp[0].length;
int[][] maxs = new int[m][n];
for(int i = 0;i < n;i++){
maxs[0][i] = i;
}
for(int j = 1;j < m;j++){
for(int i = 0;i < n;i++){
if(sp[j-1][i] != -1){
int lower = maxs[j-1][i];
int upper = maxs[j-1][sp[j-1][i]];
if(upper == -1 || pw[lower] > pw[upper]){
maxs[j][i] = lower;
}else{
maxs[j][i] = upper;
}
}else{
maxs[j][i] = -1;
}
}
}
return maxs;
}
public static int lca2(int a, int b, int[][] spar, int[] depth) {
if (depth[a] < depth[b]) {
b = ancestor(b, depth[b] - depth[a], spar);
} else if (depth[a] > depth[b]) {
a = ancestor(a, depth[a] - depth[b], spar);
}
if (a == b)
return a;
int sa = a, sb = b;
for (int low = 0, high = depth[a], t = Integer.highestOneBit(high), k = Integer
.numberOfTrailingZeros(t); t > 0; t >>>= 1, k--) {
if ((low ^ high) >= t) {
if (spar[k][sa] != spar[k][sb]) {
low |= t;
sa = spar[k][sa];
sb = spar[k][sb];
} else {
high = low | t - 1;
}
}
}
return spar[0][sa];
}
protected static int ancestor(int a, int m, int[][] spar) {
for (int i = 0; m > 0 && a != -1; m >>>= 1, i++) {
if ((m & 1) == 1)
a = spar[i][a];
}
return a;
}
public static int[][] logstepParents(int[] par) {
int n = par.length;
int m = Integer.numberOfTrailingZeros(Integer.highestOneBit(n - 1)) + 1;
int[][] pars = new int[m][n];
pars[0] = par;
for (int j = 1; j < m; j++) {
for (int i = 0; i < n; i++) {
pars[j][i] = pars[j - 1][i] == -1 ? -1 : pars[j - 1][pars[j - 1][i]];
}
}
return pars;
}
public static int[][] parents3(int[][][] g)
{
int n = g.length;
int[] par = new int[n];
Arrays.fill(par, -1);
int[] depth = new int[n];
int[] q = new int[n];
int[] pw = new int[n];
int r = 0;
for(int u = 0;u < n;u++){
if(par[u] == -1){
q[r] = u;
depth[u] = 0;
r++;
for(int p = r-1;p < r;p++) {
int cur = q[p];
for(int[] nex : g[cur]){
if(par[cur] != nex[0]){
q[r++] = nex[0];
par[nex[0]] = cur;
depth[nex[0]] = depth[cur] + 1;
pw[nex[0]] = nex[1];
}
}
}
}
}
return new int[][] {par, q, depth, pw};
}
public static int[][][] packWU(int n, int[] from, int[] to, int[] w, int sup)
{
int[][][] g = new int[n][][];
int[] p = new int[n];
for(int i = 0;i < sup;i++)p[from[i]]++;
for(int i = 0;i < sup;i++)p[to[i]]++;
for(int i = 0;i < n;i++)g[i] = new int[p[i]][2];
for(int i = 0;i < sup;i++){
--p[from[i]];
g[from[i]][p[from[i]]][0] = to[i];
g[from[i]][p[from[i]]][1] = w[i];
--p[to[i]];
g[to[i]][p[to[i]]][0] = from[i];
g[to[i]][p[to[i]]][1] = w[i];
}
return g;
}
public static class DJSet {
public int[] upper;
public List<Set<Integer>> sets;
public DJSet(int n) {
upper = new int[n];
Arrays.fill(upper, -1);
sets = new ArrayList<>();
for(int i = 0;i < n;i++)sets.add(null);
}
public DJSet(DJSet s) {
upper = Arrays.copyOf(s.upper, s.upper.length);
sets = new ArrayList<>();
int n = s.upper.length;
for(int i = 0;i < n;i++){
Set<Integer> set = s.sets.get(i);
if(set != null){
sets.add(new HashSet<>(set));
}else{
sets.add(null);
}
}
}
public int root(int x) {
return upper[x] < 0 ? x : (upper[x] = root(upper[x]));
}
public boolean equiv(int x, int y) {
return root(x) == root(y);
}
public boolean union(int x, int y) {
x = root(x);
y = root(y);
if (x != y) {
if (upper[y] < upper[x]) {
int d = x;
x = y;
y = d;
}
Set<Integer> sx = sets.get(x);
sets.set(x, null);
Set<Integer> sy = sets.get(y);
sets.set(y, null);
if(sx == null || sy == null){
}else{
if(sx.size() < sy.size()){
Set<Integer> sz = sx; sx = sy; sy = sz;
}
sx.addAll(sy);
sets.set(x, sx);
}
upper[x] += upper[y];
upper[y] = x;
}
return x == y;
}
public int count() {
int ct = 0;
for (int u : upper)
if (u < 0)
ct++;
return ct;
}
}
public static class DJSetX {
public int[] upper;
public List<Set<Integer>> sets;
public List<PriorityQueue<int[]>> pqs;
public DJSetX(int n) {
upper = new int[n];
Arrays.fill(upper, -1);
sets = new ArrayList<>();
for(int i = 0;i < n;i++)sets.add(null);
pqs = new ArrayList<>();
for(int i = 0;i < n;i++)pqs.add(null);
}
public DJSetX(DJSet s) {
upper = Arrays.copyOf(s.upper, s.upper.length);
sets = new ArrayList<>();
int n = s.upper.length;
for(int i = 0;i < n;i++){
Set<Integer> set = s.sets.get(i);
if(set != null){
sets.add(new HashSet<>(set));
}else{
sets.add(null);
}
}
}
public int root(int x) {
return upper[x] < 0 ? x : (upper[x] = root(upper[x]));
}
public boolean equiv(int x, int y) {
return root(x) == root(y);
}
public boolean union(int x, int y) {
x = root(x);
y = root(y);
if (x != y) {
if (upper[y] < upper[x]) {
int d = x;
x = y;
y = d;
}
Set<Integer> sx = sets.get(x);
sets.set(x, null);
Set<Integer> sy = sets.get(y);
sets.set(y, null);
if(sx == null || sy == null){
}else{
if(sx.size() < sy.size()){
Set<Integer> sz = sx; sx = sy; sy = sz;
}
sx.addAll(sy);
sets.set(x, sx);
}
PriorityQueue<int[]> px = pqs.get(x);
pqs.set(x, null);
PriorityQueue<int[]> py = pqs.get(y);
pqs.set(y, null);
if(px == null){
pqs.set(x, py);
}else if(py == null){
pqs.set(x, px);
}else{
if(px.size() < py.size()){
PriorityQueue<int[]> sz = px; px = py; py = sz;
}
px.addAll(py);
pqs.set(x, px);
}
upper[x] += upper[y];
upper[y] = x;
}
return x == y;
}
public int count() {
int ct = 0;
for (int u : upper)
if (u < 0)
ct++;
return ct;
}
}
void run() throws Exception
{
// int n = 100000, m = 99999;
// Random gen = new Random();
// StringBuilder sb = new StringBuilder();
// sb.append(n + " ");
// sb.append(n + " ");
// sb.append(n + " ");
// for (int i = 0; i < n; i++) {
// sb.append(gen.nextInt(200000)+1 + " ");
// }
// for (int i = 0; i < n; i++) {
// sb.append(gen.nextInt(n)+1 + " ");
// sb.append(gen.nextInt(n)+1 + " ");
// sb.append(gen.nextInt(1000000000)+1 + " ");
// }
// for (int i = 0; i < n; i++) {
// sb.append(gen.nextInt(n)+1 + " ");
// sb.append(gen.nextInt(n)+1 + " ");
// sb.append(gen.nextInt(n)+1 + " ");
// }
// INPUT = sb.toString();
is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
out = new PrintWriter(System.out);
long s = System.currentTimeMillis();
solve();
out.flush();
if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms");
}
public static void main(String[] args) throws Exception { new G3().run(); }
private byte[] inbuf = new byte[1024];
private int lenbuf = 0, ptrbuf = 0;
private int readByte()
{
if(lenbuf == -1)throw new InputMismatchException();
if(ptrbuf >= lenbuf){
ptrbuf = 0;
try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
if(lenbuf <= 0)return -1;
}
return inbuf[ptrbuf++];
}
private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
private int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }
private double nd() { return Double.parseDouble(ns()); }
private char nc() { return (char)skip(); }
private String ns()
{
int b = skip();
StringBuilder sb = new StringBuilder();
while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')
sb.appendCodePoint(b);
b = readByte();
}
return sb.toString();
}
private char[] ns(int n)
{
char[] buf = new char[n];
int b = skip(), p = 0;
while(p < n && !(isSpaceChar(b))){
buf[p++] = (char)b;
b = readByte();
}
return n == p ? buf : Arrays.copyOf(buf, p);
}
private char[][] nm(int n, int m)
{
char[][] map = new char[n][];
for(int i = 0;i < n;i++)map[i] = ns(m);
return map;
}
private int[] na(int n)
{
int[] a = new int[n];
for(int i = 0;i < n;i++)a[i] = ni();
return a;
}
private int ni()
{
int num = 0, b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}
private long nl()
{
long num = 0;
int b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}
private static void tr(Object... o) { System.out.println(Arrays.deepToString(o)); }
}
Python 3 Travel in HackerLand HackerRank 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 Travel in HackerLand HackerRank 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;
}
Leave a comment below
