Header Ad

HackerEarth Diverging Directions problem solution

In this HackerEarth Diverging Directions problem solution You are given a directed weighted graph with n nodes and 2n - 2 edges. The nodes are labeled from 1 to n, while the edges are labeled from 1 to 2n - 2. The graph's edges can be split into two parts.
  • The first n - 1 edges will form a rooted spanning tree, with node 1 as the root. All these edges will point away from the root.
  • The last n - 1 edges will be from node i to node 1, for all 2<=i<=n.
You are given q queries. There are two types of queries
  • 1iw: Change the weight of the i-th edge to w
  • 2uv: Print the length of the shortest path from node u to v
Given these queries, print the shortest path lengths.


HackerEarth Diverging Directions problem solution


HackerEarth Diverging Directions problem solution.

import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.io.BufferedWriter;
import java.util.InputMismatchException;
import java.io.IOException;
import java.util.ArrayList;
import java.util.List;
import java.util.stream.Stream;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.io.InputStream;

public class Main {
public static void main(String[] args) {
InputStream inputStream = System.in;
OutputStream outputStream = System.out;
InputReader in = new InputReader(inputStream);
OutputWriter out = new OutputWriter(outputStream);
DivergingDirections solver = new DivergingDirections();
solver.solve(1, in, out);
out.close();
}

static class DivergingDirections {
public List<DivergingDirections.Edge>[] graph;
public int[] tree_weight;
public int[] star_weight;
public int[] star_inv_weight;
public int[] tree_perm;
public int[] star_perm;
public int[] start;
public int[] end;
public int tidx;
public SegmentTreeFast root;

public void dfs(int node, int par) {
start[node] = tidx++;

for (DivergingDirections.Edge e : graph[node]) {
int next = e.to;
if (next == par) continue;
tree_perm[e.idx] = next;
dfs(next, node);
}
end[node] = tidx - 1;
}

public int getDepth(int node) {
return root.query(start[node], start[node]) - star_inv_weight[node];
}

public void solve(int testNumber, InputReader in, OutputWriter out) {
int n = in.nextInt(), q = in.nextInt();
graph = LUtils.genArrayList(n);
tree_weight = new int[n];
star_weight = new int[n];
star_inv_weight = new int[n];
tree_perm = new int[n];
star_perm = new int[n];

for (int i = 1; i <= n - 1; i++) {
int a = in.nextInt() - 1, b = in.nextInt() - 1, c = in.nextInt();
graph[a].add(new DivergingDirections.Edge(b, i));
graph[b].add(new DivergingDirections.Edge(a, i));
tree_weight[i] = c;
}

for (int i = n; i <= 2 * n - 2; i++) {
int a = in.nextInt() - 1, b = in.nextInt() - 1, c = in.nextInt();
star_weight[i - n + 1] = c;
star_perm[i - n + 1] = a;
star_inv_weight[a] = c;
}
start = new int[n];
end = new int[n];
dfs(0, -1);

root = new SegmentTreeFast(tidx);
for (int i = 1; i < n; i++) {
int node = tree_perm[i];
root.modify(start[node], end[node], tree_weight[i]);
}
for (int i = 1; i < n; i++) {
int node = star_perm[i];
root.modify(start[node], start[node], star_weight[i]);
}

while (q-- > 0) {
int type = in.nextInt();
if (type == 1) {
int edge = in.nextInt();
int new_weight = in.nextInt();
if (edge <= n - 1) {
int node = tree_perm[edge];
root.modify(start[node], end[node], new_weight - tree_weight[edge]);
tree_weight[edge] = new_weight;
} else {
edge -= n - 1;
int node = star_perm[edge];
root.modify(start[node], start[node], new_weight - star_weight[edge]);
star_weight[edge] = new_weight;
star_inv_weight[node] = new_weight;
}

} else {
int a = in.nextInt() - 1, b = in.nextInt() - 1;

int ret = getDepth(b) - getDepth(a);
if (!(start[a] <= start[b] && end[b] <= end[a])) {
ret += root.query(start[a], end[a]);
}
out.println(ret);
}
}
}

static class Edge {
public int to;
public int idx;

public Edge(int to, int idx) {
this.to = to;
this.idx = idx;
}

}

}

static class InputReader {
private InputStream stream;
private byte[] buf = new byte[1024];
private int curChar;
private int numChars;

public InputReader(InputStream stream) {
this.stream = stream;
}

public int read() {
if (this.numChars == -1) {
throw new InputMismatchException();
} else {
if (this.curChar >= this.numChars) {
this.curChar = 0;

try {
this.numChars = this.stream.read(this.buf);
} catch (IOException var2) {
throw new InputMismatchException();
}

if (this.numChars <= 0) {
return -1;
}
}

return this.buf[this.curChar++];
}
}

public int nextInt() {
int c;
for (c = this.read(); isSpaceChar(c); c = this.read()) {
;
}

byte sgn = 1;
if (c == 45) {
sgn = -1;
c = this.read();
}

int res = 0;

while (c >= 48 && c <= 57) {
res *= 10;
res += c - 48;
c = this.read();
if (isSpaceChar(c)) {
return res * sgn;
}
}

throw new InputMismatchException();
}

public static boolean isSpaceChar(int c) {
return c == 32 || c == 10 || c == 13 || c == 9 || c == -1;
}

}

static class SegmentTreeFast {
int[] value;
int[] delta;

public SegmentTreeFast(int n) {
value = new int[2 * n];
for (int i = 0; i < n; i++) {
value[i + n] = getInitValue();
}
for (int i = 2 * n - 1; i > 1; i -= 2) {
value[i >> 1] = queryOperation(value[i], value[i ^ 1]);
}
delta = new int[2 * n];
Arrays.fill(delta, getNeutralDelta());
}

int modifyOperation(int x, int y) {
return x + y;
}

int queryOperation(int leftValue, int rightValue) {
return Math.min(leftValue, rightValue);
}

int deltaEffectOnSegment(int delta, int segmentLength) {
if (delta == getNeutralDelta()) return getNeutralDelta();
// Here you must write a fast equivalent of following slow code:
// int result = delta;
// for (int i = 1; i < segmentLength; i++) result = queryOperation(result, delta);
// return result;
return delta;
}

int getNeutralDelta() {
return (1 << 29);
}

int getInitValue() {
return 0;
}

int joinValueWithDelta(int value, int delta) {
if (delta == getNeutralDelta()) return value;
return modifyOperation(value, delta);
}

int joinDeltas(int delta1, int delta2) {
if (delta1 == getNeutralDelta()) return delta2;
if (delta2 == getNeutralDelta()) return delta1;
return modifyOperation(delta1, delta2);
}

void pushDelta(int i) {
int d = 0;
for (; (i >> d) > 0; d++) {
}
for (d -= 2; d >= 0; d--) {
int x = i >> d;
value[x >> 1] = joinNodeValueWithDelta(x >> 1, 1 << (d + 1));
delta[x] = joinDeltas(delta[x], delta[x >> 1]);
delta[x ^ 1] = joinDeltas(delta[x ^ 1], delta[x >> 1]);
delta[x >> 1] = getNeutralDelta();
}
}

int joinNodeValueWithDelta(int i, int len) {
return joinValueWithDelta(value[i], deltaEffectOnSegment(delta[i], len));
}

public int query(int from, int to) {
from += value.length >> 1;
to += value.length >> 1;
pushDelta(from);
pushDelta(to);
int res = 0;
boolean found = false;
for (int len = 1; from <= to; from = (from + 1) >> 1, to = (to - 1) >> 1, len <<= 1) {
if ((from & 1) != 0) {
res = found ? queryOperation(res, joinNodeValueWithDelta(from, len)) : joinNodeValueWithDelta(from, len);
found = true;
}
if ((to & 1) == 0) {
res = found ? queryOperation(res, joinNodeValueWithDelta(to, len)) : joinNodeValueWithDelta(to, len);
found = true;
}
}
if (!found) throw new RuntimeException();
return res;
}

public void modify(int from, int to, int delta) {
from += value.length >> 1;
to += value.length >> 1;
pushDelta(from);
pushDelta(to);
int a = from;
int b = to;
for (; from <= to; from = (from + 1) >> 1, to = (to - 1) >> 1) {
if ((from & 1) != 0) {
this.delta[from] = joinDeltas(this.delta[from], delta);
}
if ((to & 1) == 0) {
this.delta[to] = joinDeltas(this.delta[to], delta);
}
}
for (int i = a, len = 1; i > 1; i >>= 1, len <<= 1) {
value[i >> 1] = queryOperation(joinNodeValueWithDelta(i, len), joinNodeValueWithDelta(i ^ 1, len));
}
for (int i = b, len = 1; i > 1; i >>= 1, len <<= 1) {
value[i >> 1] = queryOperation(joinNodeValueWithDelta(i, len), joinNodeValueWithDelta(i ^ 1, len));
}
}

}

static class OutputWriter {
private final PrintWriter writer;

public OutputWriter(OutputStream outputStream) {
writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
}

public OutputWriter(Writer writer) {
this.writer = new PrintWriter(writer);
}

public void close() {
writer.close();
}

public void println(int i) {
writer.println(i);
}

}

static class LUtils {
public static <E> List<E>[] genArrayList(int size) {
return Stream.generate(ArrayList::new).limit(size).toArray(List[]::new);
}

}
}

Post a Comment

0 Comments