HackerRank Company Retreat problem solution

In this HackerRank Company Retreat problem solution, we are given the number of employees and the retreat’s duration in days, id number of employees and we need to print a single integer denoting the minimum total cost for the M day retreat. and then print the answer with the modulo 10 to power 9 plus 7.

Problem solution in Java Programming.

import java.io.*;
import java.util.*;

public class Solution {

static final int logN = 17;
static final int INF = 1000000000;
static final int MOD = 1_000_000_007;

static int[] nxtV;
static int[] succV;
static int[] ptrV;
static int indexV = 1;

static void addV(int u, int v) {
nxtV[indexV] = ptrV[u];
ptrV[u] = indexV;
succV[indexV++] = v;
}

static int[] nxtG;
static int[] succG;
static int[] ptrG;
static int indexG = 1;

static void addG(int u, int v) {
nxtG[indexG] = ptrG[u];
ptrG[u] = indexG;
succG[indexG++] = v;
}

static int tick = 0;
static int[][] lca;
static int[] start;
static int[] dist;
static int[] depth;
static int[] d;
static int[] finish;

static class NodeDfs {
int u;
int p;
boolean start = true;
boolean flag = true;

public NodeDfs(int u, int p) {
this.u = u;
this.p = p;
}
}

static void dfs() {
Deque<NodeDfs> deque = new LinkedList<>();
deque.add(new NodeDfs(1, 0));
while (!deque.isEmpty()) {
NodeDfs node = deque.peekLast();
if (node.start) {
lca[0][node.u] = node.p;
start[node.u] = ++tick;
dist[node.u] = INF;
depth[node.u] = depth[node.p] + 1;
d[start[node.u]] = depth[node.u];
for (int i = ptrV[node.u]; i > 0; i = nxtV[i]) {
int v = succV[i];
if (v != node.p) {
node.flag = false;
deque.add(new NodeDfs(v, node.u));
}
}

node.start = false;
} else {
if (node.flag) {
dist[node.u] = 0;
}
addG(dist[node.u], node.u);
finish[node.u] = tick;

dist[node.p] = Math.min(dist[node.p], dist[node.u] + 1);

deque.removeLast();
}
}
}

static int up(int node, int k) {
for (int i = logN; i >= 0; i--) {
if ((k & (1 << i)) > 0) {
node = lca[i][node];
}
}
return node;
}

static int[] segTree;

static int update(int k, int bas, int son, int x, int y) {
if (bas > x || son < x) {
return segTree[k];
}
if (bas == son) {
return segTree[k] = (y == 1 ? d[bas] : INF);
}
return segTree[k] =
Math.min(
update(k + k, bas, (bas + son) >> 1, x, y),
update(k + k + 1, ((bas + son) >> 1) + 1, son, x, y));
}

static int query(int k, int bas, int son, int x, int y) {
if (bas > y || son < x) {
return INF;
}
if (x <= bas && son <= y) {
return segTree[k];
}
return Math.min(
query(k + k, bas, (bas + son) >> 1, x, y),
query(k + k + 1, ((bas + son) >> 1) + 1, son, x, y));
}

static class Pair implements Comparable<Pair> {

private int first;
private int second;

public Pair(int first, int second) {
this.first = first;
this.second = second;
}

public int compareTo(Pair other) {
if (first < other.first) return 1;
else if (first > other.first) return -1;
else if (second < other.second) return 1;
else if (second > other.second) return -1;
else return 0;
}
}

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

nxtV = new int[n + 1];
succV = new int[n + 1];
ptrV = new int[n + 1];

st = new StringTokenizer(br.readLine());
for (int i = 2; i <= n; i++) {
int item = Integer.parseInt(st.nextToken());
addV(item, i);
}

nxtG = new int[n + 1];
succG = new int[n + 1];
ptrG = new int[n + 1];

lca = new int[logN + 1][n + 1];
start = new int[n + 1];
dist = new int[n + 1];
depth = new int[n + 1];
d = new int[n + 1];
finish = new int[n + 1];

dfs();

for (int i = 1; i <= logN; i++) {
for (int j = 1; j <= n; j++) {
lca[i][j] = lca[i - 1][lca[i - 1][j]];
}
}

int cur = 0;
segTree = new int[(n + 1) << 2];

for (int i = 1; i <= n; i++) {
if (dist[i] == 0) {
update(1, 1, n, start[i], 1);
cur++;
} else {
update(1, 1, n, start[i], 0);
}
}

List<Integer> del = new ArrayList<>();
PriorityQueue<Pair> queue = new PriorityQueue<>();
int[] ans = new int[n + 1];

ans[1] = n;

for (int i = 2; i <= n; i++) {
int all = cur;
for (int j = ptrG[i]; j > 0; j = nxtG[j]) {
int v = succG[j];
queue.add(new Pair(depth[v], v));
}
del.clear();
while (!queue.isEmpty()) {
int node = queue.remove().second;
if (query(1, 1, n, start[node], 
finish[node]) - depth[node] < i) {
continue;
}
update(1, 1, n, start[node], 1);
all++;
del.add(node);
int up = up(node, i);
if (up > 0) {
queue.add(new Pair(depth[up], up));
}
}
ans[i] = all;
for (int j = 0; j < del.size(); j++) {
update(1, 1, n, start[del.get(j)], 0);
}
}

long result = 0;
for (int i = 1; i <= m; i++) {
st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
result = (result + (
ans[Math.min(n, y)] * (long) x) % MOD) % MOD;
}

bw.write(String.valueOf(result));
bw.newLine();

bw.close();
br.close();
}
}

Problem solution in C++ programming.

#include "bits/stdc++.h"

using namespace std;

typedef long long ll;
typedef pair < int, int > ii;

const int N = 1 << 17;
const int LOG = 17;

int n, m, tick, cnt;
int dep[N], st[N], nd[N], a[N], leaf[N];
vector < int > v[N], q[N];

int t[N << 1], sparse[LOG][N];

void up(int x, int k) {
    t[x += N] = k;
    while(x > 1) {
        x >>= 1;
        t[x] = min(t[x + x], t[x + x + 1]);
    }
}

int get(int l, int r) {
    int res = 1e9;
    for(l += N, r += N; l <= r; l = (l + 1) >> 1, r = (r - 1) >> 1) {
        if(l & 1) res = min(res, t[l]);
        if(~r & 1) res = min(res, t[r]);
    }
    return res;
}

void dfs(int p, int x) {
    st[x] = ++tick;
    dep[x] = dep[p] + 1;
    sparse[0][x] = p;
    for(int i = 1; i < LOG; i++)
        sparse[i][x] = sparse[i - 1][sparse[i - 1][x]];
    leaf[x] = 1e9;
    for(auto u : v[x]) {
        dfs(x, u);
        leaf[x] = min(leaf[x], leaf[u] + 1);
    }
    if(leaf[x] > 5e8) {
        leaf[x] = 0;
        cnt++;
    }
    q[leaf[x]].push_back(x);
    nd[x] = tick;
}

int calc(int group) {
    int res = cnt;
    priority_queue < ii > Q;
    for(auto x : q[group])
        Q.push({dep[x], x});
    vector < int > vv;
    while(!Q.empty()) {
        int x = Q.top().second;
        Q.pop();
        if(leaf[x] < group or get(st[x], nd[x]) - dep[x] < group)
            continue;
        vv.push_back(x);
        up(st[x], dep[x]);
        res++;
        if(dep[x] > group) {
            int k = group;
            for(int i = LOG - 1; i >= 0; i--) {
                if(k >= (1 << i)) {
                    k -= 1 << i;
                    x = sparse[i][x];
                }
            }
            Q.push({dep[x], x});
        }
    }
    for(auto x : vv)
        up(st[x], 1e9);
    return res;
}

int main () {

    for(int i = 1; i < N + N; i++)
        t[i] = 1e9;

    scanf("%d %d", &n, &m);

    for(int i = 2; i <= n; i++) {
        int x;
        scanf("%d", &x);
        v[x].push_back(i);
    }

    dfs(0, 1);

    for(int i = 1; i <= n; i++)
        a[i] = calc(i);

    ll ans = 0;

    for(int i = 1; i <= m; i++) {
        int x, y;
        scanf("%d %d", &x, &y);
        ans += (ll) x * a[min(n, y)];
        ans %= (int) 1e9 + 7;
    }

    printf("%lldn", ans);

    return 0;

}