Header Ad

HackerEarth Beautiful pair of nodes problem solution

In this HackerEarth Beautiful pair of nodes problem solution You are given a rooted tree having n nodes, rooted at node 1. Every node i has two values associated with itself , A[i] and B[i]. In this tree you have to count total pairs of nodes which are beautiful. A pair of nodes i , j is beautiful if i is ancestor of node j and A[i] < A[j] and B[i] < B[j].
Node i is called an ancestor of some node j, if node i is the parent of node j, or it is the ancestor of parent of node j. The root of a tree has no ancestors.


HackerEarth Beautiful pair of nodes problem solution


HackerEarth Beautiful pair of nodes problem solution.

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <bits/stdc++.h>
#define LL long long int
using namespace __gnu_pbds;
using namespace std;

typedef
tree<
pair<int,int>,
null_type,
less<pair<int,int>>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;

vector<int> graph[2000001];
set<int> temp;
bool visit[2000001];
int idx = 0;
int a[2000001];
int b[2000001];
LL final_ans = 0;


unordered_map<int,int> m;


ordered_set BIT[200001];

void remove(int pos, int val,int node)
{
while(pos <= 200000)
{
BIT[pos].erase(make_pair(val , node));
pos += (pos & (-pos));
}
}

void add(int pos,int val,int node)
{
while(pos <= 200000)
{
BIT[pos].insert(make_pair(val , node));
pos += (pos & (-pos));
}
}

void query(int pos,int val)
{

while(pos > 0)
{
final_ans = final_ans + (LL)(BIT[pos].order_of_key(make_pair(val , 0)));
pos -= (pos & (-pos));
}
}

void dfs(int node)
{
++idx;
query(m[a[node]]-1 , m[b[node]]);
add(m[a[node]] , m[b[node]] , node);
visit[node] = 1;
for(int i = 0 ; i < graph[node].size() ; i++)
{
if(visit[graph[node][i]] == 0)
{
visit[graph[node][i]] = 1;
dfs(graph[node][i]);
}
}
remove(m[a[node]] , m[b[node]] , node);
--idx;
}

#define s(x) scanf("%d",&x)

int main()
{
ios_base::sync_with_stdio(0);
int n;
s(n);
for(int i = 1 ; i <= n - 1 ; i++)
{
int u , v;
s(u);
s(v);
graph[u].push_back(v);
graph[v].push_back(u);
}
for(int i = 1 ; i <= n ; i++)
{
s(a[i]);
temp.insert(a[i]);
}
for(int i = 1 ; i <= n ; i++)
{
s(b[i]);
temp.insert(b[i]);
}
int idxs = 0;
for(int i : temp)
{
m[i] = ++idxs;
}
temp.clear();
dfs(1);
printf("%lld",final_ans);
}

Second solution

import java.io.*;
import java.util.*;
import java.math.*;
import java.util.concurrent.*;

public final class beautiful_nodes
{
static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
static FastScanner sc=new FastScanner(br);
static PrintWriter out=new PrintWriter(System.out);
static Random rnd=new Random();
static int[] x,y,cnt;
static Pair[] a;
static int[][] al;
static int time=-1;
static int[] c,tin,tout,arr;
static int maxn=(int)(1e5+5);
static int[][] bit;
static int block=3;
static int[] start,end,idx;

static void dfs(int u,int p)
{
tin[u]=++time;arr[time]=-1;

for(int x:al[u])
{
if(x!=p)
{
dfs(x,u);
}
}

tout[u]=time;
}

static void shuffle(int[] a)
{
for(int i=0;i<a.length;i++)
{
int next=rnd.nextInt(a.length);

int temp=a[i];a[i]=a[next];a[next]=temp;
}
}

static void update(int curr_idx,int val)
{
update(idx[curr_idx],val,1);

arr[curr_idx]=val;
}

static long query(int l,int r,int val)
{
long ret=0;

for(int i=idx[l]+1;i<idx[r];i++)
{
ret=ret+query(i,val+1);
}

for(int i=l;i<=Math.min(end[idx[l]],r);i++)
{
ret=ret+(arr[i]>val?1:0);
}

if(idx[l]!=idx[r])
{
for(int i=start[idx[r]];i<=r;i++)
{
ret=ret+(arr[i]>val?1:0);
}
}

return ret;
}

static void update(int idx1,int idx2,int val)
{
while(idx2>0)
{
bit[idx1][idx2]+=val;idx2-=idx2&-idx2;
}
}

static int query(int idx1,int idx2)
{
int ret=0;

while(idx2<maxn)
{
ret=ret+bit[idx1][idx2];idx2+=idx2&-idx2;
}

return ret;
}

public static void run() throws Exception
{
int n=sc.nextInt();

x=new int[n];y=new int[n];cnt=new int[n];

for(int i=1;i<n;i++)
{
x[i]=sc.nextInt()-1;y[i]=sc.nextInt()-1;

cnt[x[i]]++;cnt[y[i]]++;
}

al=new int[n][];

for(int i=0;i<n;i++)
{
al[i]=new int[cnt[i]];cnt[i]=0;
}

for(int i=1;i<n;i++)
{
int u=x[i],v=y[i];

al[u][cnt[u]++]=v;al[v][cnt[v]++]=u;
}

a=new Pair[n];c=new int[n];

for(int i=0;i<n;i++)
{
a[i]=new Pair(i,sc.nextInt(),-1);
}

for(int i=0;i<n;i++)
{
a[i].b=sc.nextInt();

c[i]=a[i].b;
}

shuffle(c);Arrays.sort(c);

for(int i=0;i<n;i++)
{
a[i].b=Arrays.binarySearch(c,a[i].b)+1;
}

tin=new int[n];tout=new int[n];arr=new int[n];dfs(0,-1);

start=new int[block];end=new int[block];idx=new int[n];bit=new int[block][maxn];

for(int i=0,j=0;i<n;i+=block,j++)
{
start[j]=i;end[j]=Math.min(n-1,i+block-1);

for(int k=start[j];k<=end[j];k++)
{
idx[k]=j;
}
}

Arrays.sort(a);int j=0;long res=0;

// out.println(Arrays.toString(tin)+" "+Arrays.toString(tout)+" "+Arrays.toString(arr));

for(int i=0;i<n;i++)
{
while(j<i && a[j].a>a[i].a)
{
update(tin[a[j].idx],a[j].b);j++;
}

long curr=query(tin[a[i].idx],tout[a[i].idx],a[i].b);

res=res+curr;

// out.println((a[i].idx+1)+" "+curr);
}

out.println(res);out.close();
}

private static class Pair implements Comparable<Pair>
{
int idx,a,b;

public Pair(int idx,int a,int b)
{
this.idx=idx;this.a=a;this.b=b;
}

public int compareTo(Pair x)
{
return -(Integer.compare(this.a,x.a));
}
}

public static void main(String[] args) throws Exception
{
new Thread(null,new Runnable(){
public void run()
{
try
{
new beautiful_nodes().run();
}
catch(Exception e)
{

}
}
},"1",1<<26).start();
}
}
class FastScanner
{
BufferedReader in;
StringTokenizer st;

public FastScanner(BufferedReader in) {
this.in = in;
}

public String nextToken() throws Exception {
while (st == null || !st.hasMoreTokens()) {
st = new StringTokenizer(in.readLine());
}
return st.nextToken();
}

public String next() throws Exception {
return nextToken().toString();
}

public int nextInt() throws Exception {
return Integer.parseInt(nextToken());
}

public long nextLong() throws Exception {
return Long.parseLong(nextToken());
}

public double nextDouble() throws Exception {
return Double.parseDouble(nextToken());
}
}

Post a Comment

0 Comments