HackerRank DAG Queries Problem Solution Yashwant Parihar, May 22, 2023May 28, 2024 In this post, we will solve HackerRank DAG Queries Problem Solution. You are given a Directed Acyclic Graph (DAG) with n vertices and m edges. Each vertex v has an integer, a,, associated with it and the initial value of a, is 0 for all vertices. You must perform q queries on the DAG, where each query is one of the following types: 1. 1 u x: Seta, to æ for all v such that there is a path in the DAG from u to v. 2.2 u x: Seta, to æ for all v such that there is a path from u to v and a, > x. 3.3 u: Print the value of a,, on a new line.Input FormatThe first line contains three space-separated integers describing the respective values of n (the number of vertices in the DAG), m (the number of edges in the DAG), and g (the number of queries to perform).Each of the m subsequent lines contains two space-separated integers describing the respective values of u and u (where 1 <u, v < n. uv) denoting a directed edge from vertex u to vertex in the graph.Each of the q subsequent lines contains a query in one of the three formats described above. Output Format For each query of type a (i.e., 3 u), print the value of au on a new line. Sample Input 0 6 5 18 1 2 1 3 3 4 2 4 5 6 1 1 3 3 1 3 2 3 3 3 4 1 2 2 3 1 3 2 3 3 3 4 2 6 7 3 5 3 6 2 1 3 3 1 3 2 3 3 3 4 Sample Output 0 3 3 3 3 3 2 3 2 0 0 3 2 3 2 HackerRank DAG Queries Problem Solution DAG Queries C++ Solution #include <bits/stdc++.h> using namespace std; #define sz(x) ((int) (x).size()) #define forn(i,n) for (int i = 0; i < int(n); ++i) typedef long long ll; typedef long long i64; typedef long double ld; typedef pair<int, int> pii; const int inf = int(1e9) + int(1e5); const ll infl = ll(2e18) + ll(1e10); #define tm suka const int maxc = 1e9; //const int maxn = 1001; const int maxn = 100100; vector<int> g[maxn]; int tm[maxn]; int qt[maxn]; int qu[maxn]; int qx[maxn]; int qans[maxn]; //const int sn = 1; const int sn = 600; const int sn2 = 1000; const int block = maxn / 3 + 2; bitset<block> bs[maxn]; bool used[maxn]; int L, R; int n; vector<int> ord; void pre(int u) { used[u] = true; for (int v: g[u]) if (!used[v]) pre(v); ord.push_back(u); } void uin(int &a, int b) { a = min(a, b); } void uax(int &a, int b) { a = max(a, b); } int a[maxn / sn + 2][maxn]; int upd[maxn]; vector<pii> o; void put1(int u, int x) { o.emplace_back(u, x); if (sz(o) < sn2) return; forn (i, n) upd[i] = -1; for (auto p: o) uax(upd[p.first], p.second); o.clear(); for (int ii = n - 1; ii >= 0; --ii) { int u = ord[ii]; tm[u] = max(tm[u], upd[u]); for (int v: g[u]) uax(upd[v], upd[u]); } } int get1(int u) { int res = tm[u]; for (auto op: o) if (bs[op.first][u - L]) uax(res, op.second); return res; } vector<int> q2; void calc2(int l, int r) { int k = l / sn; forn (i, n) a[k][i] = maxc; for (int i = l; i < r; ++i) { int id = q2[i]; uin(a[k][qu[id]], qx[id]); } for (int ii = n - 1; ii >= 0; --ii) { int u = ord[ii]; for (int v: g[u]) uin(a[k][v], a[k][u]); } } int get2(int u, int l, int r) { l = lower_bound(q2.begin(), q2.end(), l) - q2.begin(); r = lower_bound(q2.begin(), q2.end(), r) - q2.begin(); int res = maxc; int l2 = ((l + sn - 1) / sn) * sn; int r2 = (r / sn) * sn; if (l2 > r2) { for (int i = l; i < r; ++i) { int id = q2[i]; int v = qu[id]; if (bs[v][u - L]) uin(res, qx[id]); } } else { for (int i = l; i < l2; ++i) { int id = q2[i]; int v = qu[id]; if (bs[v][u - L]) uin(res, qx[id]); } for (int i = r2; i < r; ++i) { int id = q2[i]; int v = qu[id]; if (bs[v][u - L]) uin(res, qx[id]); } l2 /= sn, r2 /= sn; for (int i = l2; i < r2; ++i) uin(res, a[i][u]); } return res; } int main() { #ifdef LOCAL assert(freopen("test.in", "r", stdin)); #endif int m, q; cin >> n >> m >> q; forn (i, m) { int u, v; scanf("%d%d", &u, &v); --u, --v; g[u].push_back(v); } forn (i, n) if (!used[i]) pre(i); forn (i, q) { int t, u, x = -1; scanf("%d%d", &t, &u); --u; if (t != 3) scanf("%d", &x); qt[i] = t, qu[i] = u, qx[i] = x; } forn (i, q) { if (qt[i] != 2) continue; q2.push_back(i); } for (int i = 0; i + sn <= sz(q2); i += sn) calc2(i, i + sn); for (L = 0; L < n; L += block) { R = min(n, L + block); forn (i, n) { bs[i].reset(); tm[i] = -1; } o.clear(); forn (i, n) { int u = ord[i]; if (L <= u && u < R) bs[u][u - L] = true; for (int v: g[u]) bs[u] |= bs[v]; } forn (id, q) { if (qt[id] == 3) { int u = qu[id]; if (u < L || u >= R) continue; int lb = get1(u); int val = lb >= 0 ? qx[lb] : 0; uin(val, get2(u, lb, id)); qans[id] = val; } if (qt[id] == 1) put1(qu[id], id); } } forn (i, q) { if (qt[i] == 3) cout << qans[i] << '\n'; } } DAG Queries Scala Solution object Assert { def check(e: Boolean) { if (!e) { throw new AssertionError(); } } } class Scanner(is: java.io.InputStream) { val buffer: Array[Byte] = new Array[Byte](1 << 16); var len: Int = 0; var pos: Int = 0; def nextChar(): Int = { if (pos == len) { val read: Int = is.read(buffer); if (read == -1) { return -1; } len = read; pos = 0; } Assert.check(pos < len); val value: Int = buffer(pos) & 0xFF; pos += 1; return value; } def nextInt(): Int = { var c: Int = nextChar(); while (c == ' ' || c == '\n' || c == '\r' || c == '\t') { c = nextChar(); } Assert.check('0' <= c && c <= '9'); var value: Int = c - '0'; c = nextChar(); while ('0' <= c && c <= '9') { val digit: Int = c - '0'; Assert.check(value < Int.MaxValue / 10 || value == Int.MaxValue / 10 && digit <= Int.MaxValue % 10); value = value * 10 + digit; c = nextChar(); } return value; } } class IntArrayList { var a: Array[Int] = new Array[Int](4); var size: Int = 0; def add(x: Int): Unit = { if (size == a.length) { a = java.util.Arrays.copyOf(a, a.length * 2); } a(size) = x; size += 1; } def get(i: Int): Int = { Assert.check(i < size); return a(i); } } class Query(val typ: Int, val node: Int, val value: Int) {} object Solution { def reorder(parents: Array[IntArrayList], queries: Array[Query]): Unit = { val nV: Int = parents.size; val startOrder: Array[Int] = new Array[Int](nV); { var i: Int = 0; while (i < nV) { startOrder(i) = i; i += 1; } } var rnd: java.util.Random = new java.util.Random(20161106); { var i: Int = nV - 1; while (i > 0) { val j: Int = rnd.nextInt(i + 1); val t: Int = startOrder(i); startOrder(i) = startOrder(j); startOrder(j) = t; i -= 1; } } val orderedId: Array[Int] = new Array[Int](nV); java.util.Arrays.fill(orderedId, -1); val stack: IntArrayList = new IntArrayList(); val ip: IntArrayList = new IntArrayList(); var nextId: Int = 0; { var i: Int = 0; while (i < nV) { if (orderedId(startOrder(i)) == -1) { stack.add(startOrder(i)); ip.add(0); while (stack.size > 0) { val cur: Int = stack.a(stack.size - 1); if (ip.get(ip.size - 1) == parents(cur).size) { orderedId(cur) = nextId; nextId += 1; stack.size -= 1; ip.size -= 1; } else { val p: Int = parents(cur).get(ip.get(ip.size - 1)); ip.a(ip.size - 1) += 1; if (orderedId(p) == -1) { stack.add(p); ip.add(0); } } } } i += 1; } } if (false) { print("new ids: "); var first: Boolean = true; { var i: Int = 0; while (i < nV) { if (first) { first = false; } else { print(", "); } print((i + 1) + " -> " + (orderedId(i) + 1)); i += 1; } } println(); } Assert.check(nextId == nV); { var i: Int = 0; while (i < orderedId.length) { Assert.check(orderedId(i) >= 0); i += 1; } } val orderedParents: Array[IntArrayList] = new Array[IntArrayList](nV); { var i: Int = 0; while (i < nV) { orderedParents(i) = new IntArrayList(); i += 1; } } { var i: Int = 0; while (i < nV) { { var ip: Int = 0; while (ip < parents(i).size) { val p: Int = parents(i).get(ip); orderedParents(orderedId(i)).add(orderedId(p)); ip += 1; } } i += 1; } } { var i: Int = 0; while (i < nV) { java.util.Arrays.sort(orderedParents(i).a, 0, orderedParents(i).size); parents(i) = orderedParents(i); i += 1; } } { var i: Int = 0; while (i < queries.length) { val typ: Int = queries(i).typ; val node: Int = queries(i).node; val value: Int = queries(i).value; Assert.check(0 <= node && node < nV); queries(i) = new Query(typ, orderedId(node), value); i += 1; } } } def process( parents: Array[IntArrayList], queries: Array[Query], qFirst: Int, qAfter: Int, a: Array[Int], codes: Array[Long], add: Array[Int], min: Array[Int], result: IntArrayList ): Unit = { val nV: Int = parents.length; val q12: IntArrayList = new IntArrayList(); { var q = qFirst; while (q < qAfter) { if (queries(q).typ < 3) { q12.add(q); } q += 1; } } if (q12.size == 0) { var q: Int = qFirst; while (q < qAfter) { Assert.check(queries(q).typ == 3); val node: Int = queries(q).node; Assert.check(0 <= node && node < nV); result.add(a(node)); q += 1; } return; } val n: Int = q12.size; Assert.check(n <= 8 * 14); Assert.check(nV <= 100000); java.util.Arrays.fill(codes, 0, nV * 2, 0); { var i: Int = 0; while (i < n) { val node: Int = queries(q12.get(i)).node; val word: Int = i / 56; val shift: Int = i % 56 / 14 * 16 + i % 14; // 14 used bits, 2 free codes(node * 2 + word) |= 1L << shift; i += 1; } } { var i: Int = 0; while (i < nV) { { val pari: IntArrayList = parents(i); var ip: Int = 0; while (ip < pari.size) { val p: Int = pari.get(ip); codes((i << 1) + 0) |= codes((p << 1) + 0); codes((i << 1) + 1) |= codes((p << 1) + 1); ip += 1; } } i += 1; } } var q: Int = qFirst; var part: Int = 0; while (part * 14 < n) { val begin: Int = part * 14; val end: Int = Math.min(n, begin + 14); val codesAdd: Int = part / 4; val codesShift: Int = part % 4 * 16; // a = Math.min(a + add, min) add(0) = 0; min(0) = 1000 * 1000 * 1000; var bit: Int = 0; while (bit < end - begin) { val qType: Int = queries(q12.get(begin + bit)).typ; val value: Int = queries(q12.get(begin + bit)).value; val extra: Int = 1 << bit; if (qType == 1) { // assign var code: Int = 0; while (code < extra) { add(code + extra) = 1000 * 1000 * 1000; min(code + extra) = value; code += 1; } } else { Assert.check(qType == 2); // min var code: Int = 0; while (code < extra) { add(code + extra) = add(code); min(code + extra) = Math.min(value, min(code)); code += 1; } } bit += 1; } var mask = 0; while (end == n && q != qAfter || end != n && q != q12.get(end)) { if (queries(q).typ < 3) { mask <<= 1; mask |= 1; } else { Assert.check(queries(q).typ == 3); val node: Int = queries(q).node; val code: Int = ((codes((node << 1) + codesAdd) >> codesShift) & mask).toInt; val answer: Int = Math.min(a(node) + add(code), min(code)); result.add(answer); } q += 1; } var i = 0; while (i < nV) { val code: Int = ((codes((i << 1) + codesAdd) >> codesShift) & 0xFFFF).toInt; a(i) = Math.min(a(i) + add(code), min(code)); i += 1; } part += 1; } } def solveFast(parents: Array[IntArrayList], queries: Array[Query]): IntArrayList = { val nV: Int = parents.length; { var i: Int = 0; while (i < nV) { { var ip: Int = 0; while (ip < parents(i).size) { val p: Int = parents(i).get(ip); Assert.check(p < i); // parents before children ip += 1; } } i += 1; } } val a: Array[Int] = new Array[Int](nV); val codes: Array[Long] = new Array[Long](100000 * 2); val add: Array[Int] = new Array[Int](1 << 14); val min: Array[Int] = new Array[Int](1 << 14); val result: IntArrayList = new IntArrayList(); val MAX12Q = 8 * 14; var first: Int = 0; var n12q: Int = 0; val nQ: Int = queries.length; { var i: Int = 0; while (i < nQ) { if (queries(i).typ < 3) { n12q += 1; } if (n12q == MAX12Q || i == nQ - 1) { process(parents, queries, first, i + 1, a, codes, add, min, result); first = i + 1; n12q = 0; } i += 1; } } return result; } def main(args: Array[String]): Unit = { val in: Scanner = new Scanner(System.in); val nV: Int = in.nextInt(); val nE: Int = in.nextInt(); val nQ: Int = in.nextInt(); val parents: Array[IntArrayList] = new Array[IntArrayList](nV); { var i: Int = 0; while (i < nV) { parents(i) = new IntArrayList(); i += 1; } } { var i: Int = 0; while (i < nE) { val parent: Int = in.nextInt() - 1; val child: Int = in.nextInt() - 1; parents(child).add(parent); i += 1; } } val queries: Array[Query] = new Array[Query](nQ); { var i: Int = 0; while (i < nQ) { val qType: Int = in.nextInt(); if (qType == 1 || qType == 2) { val parent: Int = in.nextInt() - 1; val value: Int = in.nextInt(); queries(i) = new Query(qType, parent, value); } else { Assert.check(qType == 3); val node: Int = in.nextInt() - 1; queries(i) = new Query(qType, node, -1); } i += 1; } } reorder(parents, queries); val result: IntArrayList = solveFast(parents, queries); { var i: Int = 0; while (i < result.size) { println(result.get(i)); i += 1; } } } } DAG Queries Java Solution import java.io.*; import java.util.*; public class Solution { static class MyBitSet { private final static int ADDRESS_BITS_PER_WORD = 6; private long[] words; private transient int wordsInUse = 0; private static int wordIndex(int bitIndex) { return bitIndex >> ADDRESS_BITS_PER_WORD; } public MyBitSet(int nbits) { words = new long[wordIndex(nbits - 1) + 1]; } public void clear() { while (wordsInUse > 0) words[--wordsInUse] = 0; } public void set(int bitIndex) { int wordIndex = wordIndex(bitIndex); expandTo(wordIndex); words[wordIndex] |= (1L << bitIndex); } private void expandTo(int wordIndex) { int wordsRequired = wordIndex + 1; if (wordsInUse < wordsRequired) { wordsInUse = wordsRequired; } } public void or(MyBitSet set) { int wordsInCommon = Math.min(wordsInUse, set.wordsInUse); if (wordsInUse < set.wordsInUse) { wordsInUse = set.wordsInUse; } for (int i = 0; i < wordsInCommon; i++) { words[i] |= set.words[i]; } if (wordsInCommon < set.wordsInUse) { System.arraycopy(set.words, wordsInCommon, words, wordsInCommon, wordsInUse - wordsInCommon); } } public boolean get(int bitIndex) { int wordIndex = wordIndex(bitIndex); return (wordIndex < wordsInUse) && ((words[wordIndex] & (1L << bitIndex)) != 0); } } static class PS { int opt; int u; int x; int i; } static class QS { int u; int i; public QS(int u, int i) { this.u = u; this.i = i; } } static Set<Integer>[] graph; static int[] indeg; static int[] topo; static int ttot = 1; static void topo_dfs(int node) { topo[ttot++] = node; for (int i = ptr[node]; i > 0; i = nxt[i]) { if (--indeg[succ[i]] == 0) { topo_dfs(succ[i]); } } } static int[] nxt; static int[] succ; static int[] ptr; static int index = 1; static void addedge(int u, int v) { nxt[index] = ptr[u]; ptr[u] = index; succ[index++] = v; } static final int B = 316; static int[] solve2(int[][] queries, int n, int nQue) { int q = queries[0].length - 1; int[] ans = new int[q + 1]; QS[] que = new QS[nQue + 1]; PS[] perform = new PS[q + 1]; int ptot = 0; int qtot = 0; for (int i = 1; i <= q; i++) { perform[ptot] = new PS(); perform[ptot].opt = queries[0][i]; if (perform[ptot].opt <= 2) { perform[ptot].u = queries[1][i]; perform[ptot].x = queries[2][i]; perform[ptot++].i = i; } else { que[qtot++] = new QS(queries[1][i], i); } ans[i] = Integer.MAX_VALUE; } MyBitSet[] b = new MyBitSet[n + 1]; for (int i = n; i > 0; i--) { b[i] = new MyBitSet(320); } boolean[] cover = new boolean[n + 1]; int[] minVal = new int[n + 1]; for (int l = (ptot - 1) - (ptot - 1) % B, r = ptot - 1; l >= 0; r = l - 1, l -= B) { for (int i = n; i > 0; i--) { b[i].clear(); } for (int i = l; i <= r; ++i) { b[perform[i].u].set(i - l); } for (int i = 1; i <= n; i++) { for (int j = ptr[topo[i]]; j > 0; j = nxt[j]) { b[succ[j]].or(b[topo[i]]); } } Arrays.fill(cover, false); for (int i = l; i <= r; i++) { if (perform[i].opt == 1) { cover[perform[i].u] = true; } } for (int i = 1; i <= n; i++) { if (cover[topo[i]]) { for (int j = ptr[topo[i]]; j > 0; j = nxt[j]) { cover[succ[j]] = true; } } } Arrays.fill(minVal, Integer.MAX_VALUE); for (int i = l; i <= r; i++) { if (perform[i].opt == 2) { minVal[perform[i].u] = Math.min(minVal[perform[i].u], perform[i].x); } } for (int i = 1; i <= n; ++i) { for (int j = ptr[topo[i]]; j > 0; j = nxt[j]) { minVal[succ[j]] = Math.min(minVal[succ[j]], minVal[topo[i]]); } } int i = qtot; while (i > 0 && que[i - 1].i > perform[l].i) { i--; } while (i < qtot) { if (que[i].i < perform[r].i) { int j = r; while (perform[j].i > que[i].i) { --j; } for (; j >= l; j--) if (b[que[i].u].get(j - l)) { ans[que[i].i] = Math.min(ans[que[i].i], perform[j].x); if (perform[j].opt == 1) { --qtot; QS temp = que[i]; que[i] = que[qtot]; que[qtot] = temp; break; } } i += j < l ? 1 : 0; } else if (cover[que[i].u]) { int j = r; for (; perform[j].opt == 2 || !b[que[i].u].get(j - l); j--) { if (perform[j].opt == 2 && b[que[i].u].get(j - l)) { ans[que[i].i] = Math.min(ans[que[i].i], perform[j].x); } } ans[que[i].i] = Math.min(ans[que[i].i], perform[j].x); --qtot; QS temp = que[i]; que[i] = que[qtot]; que[qtot] = temp; } else { ans[que[i].i] = Math.min(ans[que[i].i], minVal[que[i].u]); i++; } } } while (qtot-- > 0) { ans[que[qtot].i] = 0; } return ans; } 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()); int q = Integer.parseInt(st.nextToken()); graph = new Set[n + 1]; Set<Integer>[] parent = new Set[n + 1]; for (int i = 1; i <= n; i++) { graph[i] = new HashSet<>(); parent[i] = new HashSet<>(); } for (int i = 0; i < m; i++) { st = new StringTokenizer(br.readLine()); int u = Integer.parseInt(st.nextToken()); int v = Integer.parseInt(st.nextToken()); graph[u].add(v); parent[v].add(u); } int[][] queries = new int[3][q + 1]; int[] convert = new int[n + 1]; int nodes = 0; int op3 = 0; for (int i = 1; i <= q; i++) { st = new StringTokenizer(br.readLine()); queries[0][i] = Integer.parseInt(st.nextToken()); int u = Integer.parseInt(st.nextToken()); if (convert[u] == 0) { nodes++; convert[u] = nodes; } queries[1][i] = convert[u]; if (queries[0][i] <= 2) { int x = Integer.parseInt(st.nextToken()); queries[2][i] = x; } else { op3++; } } for (int u = 1; u <= n; u++) { if (convert[u] == 0) { for (int v : parent[u]) { graph[v].remove(u); graph[v].addAll(graph[u]); } for (int v : graph[u]) { parent[v].remove(u); parent[v].addAll(parent[u]); } parent[u] = null; graph[u] = null; } } indeg = new int[nodes + 1]; boolean[] existDeg = new boolean[nodes + 1]; nxt = new int[m + 1]; ptr = new int[nodes + 1]; succ = new int[m + 1]; for (int u1 = 1; u1 <= n; u1++) { int u = convert[u1]; if (u > 0) { for (int v1 : graph[u1]) { int v = convert[v1]; indeg[v]++; existDeg[v] = true; addedge(u, v); } } } topo = new int[nodes + 1]; for (int i = nodes; i > 0; i--) { if (!existDeg[i]) { topo_dfs(i); } } int[] ans = solve2(queries, nodes, op3); for (int i = 1; i <= q; i++) { if (ans[i] < Integer.MAX_VALUE) { bw.write(ans[i] + "\n"); } } bw.close(); br.close(); } } C++ HackerRank Solutions java Scala cppHackerrank SolutionsjavaScala