HackerRank Ticket to Ride problem solution

In this HackerRank Ticket to Ride problem we have given n road plans and m ticket prices, help Simon by printing the value of his maximum possible profit on a new line.

Problem solution in Java Programming.

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

public class Solution {

  static final int BASE = 1 << 19;
  static long[] t = new long[BASE * 2];
  static long[] upd = new long[BASE * 2];

  static long get() {
    return t[1] + upd[1];
  }

  static int l, r, delta;

  static void put(int v, int cl, int cr) {
    if (r <= cl || cr <= l) {
      return;
    }
    if (l <= cl && cr <= r) {
      upd[v] += delta;
      return;
    }
    int cc = (cl + cr) >> 1;
    put(v << 1, cl, cc);
    put((v << 1) + 1, cc, cr);
    t[v] = Math.max(t[v << 1] + upd[v << 1], t[(v << 1) + 1] + upd[(v << 1) + 1]);
  }

  static int[] in;
  static int[] out;

  static void add(int v, int deltat) {
    l = in[v];
    r = out[v];
    delta = deltat;
    put(1, 0, BASE);
  }

  static boolean isPrev(int u, int v) {
    return in[u] <= in[v] && out[v] <= out[u];
  }

  static class Pair {
    int first;
    int second;

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

  static List<Pair>[] other;
  static List<Pair>[] down;
  static List<Pair>[] up;
  static List<Pair>[] g;

  static long best = 0;

  static class NodeGo {
    int u;
    int prev;
    Pair p;
    boolean start = true;

    public NodeGo(int u, int prev, Pair p) {
      this.u = u;
      this.prev = prev;
      this.p = p;
    }
  }

  static void go() {
    Deque<NodeGo> deque = new LinkedList<>();
    deque.add(new NodeGo(0, 0, null));

    while (!deque.isEmpty()) {
      NodeGo node = deque.peekLast();

      if (node.start) {
        if (node.p != null) {
          add(node.p.first, 2 * node.p.second);
          upd[1] -= node.p.second;
        }

        for (Pair p : other[node.u]) {
          add(p.first, p.second);
        }
        for (Pair p : down[node.u]) {
          add(p.first, -p.second);
          upd[1] += p.second;
        }
        for (Pair p : up[node.u]) {
          add(p.first, -p.second);
        }
        best = Math.max(best, get());

        for (Pair p : g[node.u]) {
          if (p.first == node.prev) {
            continue;
          }
          deque.add(new NodeGo(p.first, node.u, p));
        }

        node.start = false;
      } else {
        for (Pair p : other[node.u]) {
          add(p.first, -p.second);
        }
        for (Pair p : down[node.u]) {
          add(p.first, p.second);
          upd[1] -= p.second;
        }
        for (Pair p : up[node.u]) {
          add(p.first, p.second);
        }

        if (node.p != null) {
          add(node.p.first, -2 * node.p.second);
          upd[1] += node.p.second;
        }

        deque.removeLast();
      }
    }
  }

  static int sc = 0;
  static int[] st;
  static int[] visits;
  static int[] needh;
  static int[] step;
  static int timer = 0;
  static List<Integer>[] endings;

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

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

  static void dfs() {
    Deque<NodeDfs> deque = new LinkedList<>();
    deque.add(new NodeDfs(0, 0, 0));

    while (!deque.isEmpty()) {
      NodeDfs node = deque.peekLast();

      if (node.start) {
        st[sc++] = node.u;
        for (int id : endings[node.u]) {
          visits[id]++;
          if (visits[id] == 1) {
            needh[id] = sc;
          } else if (visits[id] == 2) {
            step[id] = st[needh[id]];
          }
        }
        in[node.u] = timer++;
        t[in[node.u] + BASE] = -node.depth;

        for (Pair p : g[node.u]) {
          if (p.first != node.p) {
            deque.add(new NodeDfs(p.first, node.u, node.depth + p.second));
          }
        }

        node.start = false;
      } else {
        for (int id : endings[node.u]) {
          visits[id]--;
        }
        out[node.u] = timer;
        --sc;

        deque.removeLast();
      }
    }
  }

  @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 stk = new StringTokenizer(br.readLine());
    int n = Integer.parseInt(stk.nextToken());

    other = new List[n];
    down = new List[n];
    up = new List[n];
    g = new List[n];
    endings = new List[n];

    for (int i = 0; i < g.length; i++) {
      g[i] = new ArrayList<>();
      endings[i] = new ArrayList<>();
      other[i] = new ArrayList<>();
      up[i] = new ArrayList<>();
      down[i] = new ArrayList<>();
    }

    for (int i = 0; i < n - 1; i++) {
      stk = new StringTokenizer(br.readLine());
      int u = Integer.parseInt(stk.nextToken()) - 1;
      int v = Integer.parseInt(stk.nextToken()) - 1;
      int l = Integer.parseInt(stk.nextToken());
      g[u].add(new Pair(v, l));
      g[v].add(new Pair(u, l));
    }

    stk = new StringTokenizer(br.readLine());
    int m = Integer.parseInt(stk.nextToken());
    Pair[] tickets = new Pair[m];
    int[] ticket_cost = new int[m];

    for (int i = 0; i < m; i++) {
      stk = new StringTokenizer(br.readLine());
      int u = Integer.parseInt(stk.nextToken()) - 1;
      int v = Integer.parseInt(stk.nextToken()) - 1;
      int c = Integer.parseInt(stk.nextToken());
      endings[u].add(i);
      endings[v].add(i);
      tickets[i] = new Pair(u, v);
      ticket_cost[i] = c;
    }

    step = new int[m];
    Arrays.fill(step, -1);
    in = new int[n];
    out = new int[n];
    st = new int[n];
    visits = new int[m];
    needh = new int[m];

    dfs();
    for (int i = BASE - 1; i > 0; --i) {
      t[i] = Math.max(t[i * 2], t[i * 2 + 1]);
    }

    for (int i = 0; i < m; i++) {
      int u = tickets[i].first;
      int v = tickets[i].second;
      int c = ticket_cost[i];
      if (isPrev(v, u)) {
        int temp = u;
        u = v;
        v = temp;
      }
      if (isPrev(u, v)) {
        u = step[i];
        add(v, c);
        up[u].add(new Pair(v, c));
        down[v].add(new Pair(u, c));
      } else {
        other[u].add(new Pair(v, c));
        other[v].add(new Pair(u, c));
      }
    }
    go();

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

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

Problem solution in C++ programming.

#include <algorithm>
#include <climits>
#include <iostream>
#include <type_traits>
#include <utility>
#include <vector>
using namespace std;

#define FOR(i, a, b) for (remove_cv<remove_reference<decltype(b)>::type>::type i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define ROF(i, a, b) for (remove_cv<remove_reference<decltype(b)>::type>::type i = (b); --i >= (a); )

const long N = 200000, NN = 1 << 63-__builtin_clzl(N-1)+1, M = 100000;
long st[N], dep[N], pre[N], post[N], tick, mx[2*NN], dlt[2*NN], opt;
vector<pair<long, long>> adj[N], ticket[N], other[N], down[N], up[N];

void mconcat(long i)
{
  mx[i] = max(mx[2*i]+dlt[2*i], mx[2*i+1]+dlt[2*i+1]);
}

void add(long u, long x)
{
  bool lf = false, rf = false;
  long l = NN+pre[u], r = NN+post[u];
  while (l < r) {
    if (l & 1) lf = true, dlt[l++] += x;
    l >>= 1;
    if (lf) mconcat(l-1);
    if (r & 1) rf = true, dlt[--r] += x;
    r >>= 1;
    if (rf) mconcat(r);
  }
  for (l--; l >>= 1, r >>= 1; ) {
    if (lf || l == r) mconcat(l);
    if (rf && l != r) mconcat(r);
  }
}

void dfs(long d, long sum, long u)
{
  dep[u] = d;
  st[d] = u;
  mx[NN+tick] = - sum;
  pre[u] = tick++;
  post[u] = LONG_MAX;
  long x = 0;
  for (auto e: ticket[u])
    if (post[e.first]) {
      long v = e.first, cost = e.second;
      if (post[v] == LONG_MAX) {
        long w = st[dep[v]+1];
        down[w].emplace_back(u, cost);
        up[u].emplace_back(w, cost);
        x += cost;
      } else {
        other[u].emplace_back(v, cost);
        other[v].emplace_back(u, cost);
      }
    }
  for (auto e: adj[u])
    if (! post[e.first])
      dfs(d+1, sum+e.second, e.first);
  post[u] = tick;
  add(u, x);
}

void calc(long u, long p)
{
  for (auto e: other[u])
    add(e.first, e.second);
  for (auto e: down[u])
    add(e.first, - e.second);
  for (auto e: up[u]) {
    dlt[1] += e.second;
    add(e.first, - e.second);
  }
  opt = max(opt, mx[1]+dlt[1]);
  for (auto e: adj[u])
    if (e.first != p) {
      dlt[1] -= e.second;
      add(e.first, 2*e.second);
      calc(e.first, u);
      dlt[1] += e.second;
      add(e.first, -2*e.second);
    }
  for (auto e: other[u])
    add(e.first, - e.second);
  for (auto e: down[u])
    add(e.first, e.second);
  for (auto e: up[u]) {
    dlt[1] -= e.second;
    add(e.first, e.second);
  }
}

int main()
{
  ios_base::sync_with_stdio(0);
  long n, m, u, v, w;
  cin >> n;
  REP(i, n-1) {
    cin >> u >> v >> w;
    u--, v--;
    adj[u].emplace_back(v, w);
    adj[v].emplace_back(u, w);
  }
  cin >> m;
  REP(i, m) {
    cin >> u >> v >> w;
    u--, v--;
    ticket[u].emplace_back(v, w);
    ticket[v].emplace_back(u, w);
  }
  dfs(0, 0, 0);
  ROF(i, 1, NN)
    mconcat(i);
  calc(0, -1);
  cout << opt << endl;
}