DAG Queries – HackerRank Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
Solutions of Algorithms Data Structures Hard HackerRank:
Here are all the Solutions of Hard , Advanced , Expert Algorithms of Data Structure of Hacker Rank , Leave a comment for similar posts
C++ DAG Queries HackerRank Solution
#include <map>
#include <vector>
#include <queue>
#include <cstdio>
#include <iterator>
#include <functional>
#include <new>
#include <array>
namespace XX
{
template<int BLOCKSIZE>
class MemoryManager
{
public:
static constexpr const int INIT = 1024 * 1024 / BLOCKSIZE? 1024 * 1024 / BLOCKSIZE: 1;
static MemoryManager* inst()
{
static MemoryManager ret;
return &ret;
}
void* alloc()
{
void* ret;
if(_ptr)
{
ret = _ptr;
_ptr = *static_cast<void**>(_ptr);
}
else
{
if(_pos == _size)
{
_pos = 0;
_buf[++_idx] = new char[_size <<= 1];
}
ret = _buf[_idx] + _pos;
_pos += BLOCKSIZE;
}
return ret;
}
void dealloc(void* p)
{
*static_cast<void**>(p) = _ptr;
_ptr = p;
}
~MemoryManager()
{
for(int i = 1; i <= _idx; i++)
delete []_buf[i];
}
private:
MemoryManager() { _buf[0] = _init; }
char _init[INIT * BLOCKSIZE];
int _size = INIT * BLOCKSIZE;
int _idx = 0;
int _pos = 0;
char* _buf[32] = {};
void* _ptr = nullptr;
};
template<typename T>
struct BlockAllocater
{
void* operator new(std::size_t count) { return MemoryManager<sizeof(T)>::inst()->alloc(); }
void operator delete(void* ptr) { return MemoryManager<sizeof(T)>::inst()->dealloc(ptr); }
};
template<typename T>
struct NullNode
{
static T nullnode;
static T* null() { return &nullnode; }
bool isNull(){return this == null();}
};
template<typename T>
T NullNode<T>::nullnode;
}
#ifdef _MSC_VER
#include <intrin.h>
inline int CLZ(int n){unsigned long ret; _BitScanForward(&ret, n); return ret;}
//inline int CLZ(long long int n){unsigned long ret; _BitScanForward64(&ret, n); return ret;}
inline int CTZ(int n){unsigned long ret; _BitScanReverse( &ret, n); return 31 - ret;}
//inline int CTZ(long long int n){unsigned long ret; _BitScanReverse64( &ret, n); return 63 - ret;}
inline int POPCNT(int n){return __popcnt(n);}
//inline int POPCNT(long long int n){return __popcnt64(n);}
#endif
#ifdef __GNUC__
inline int CLZ(int n){return __builtin_clz(n);}
inline int CLZLL(long long int n){return __builtin_clzll(n);}
inline int CTZ(int n){return __builtin_ctz(n);}
inline int CTZLL(long long int n){return __builtin_ctzll(n);}
inline int POPCNT(int n){return __builtin_popcount(n);}
inline int POPCNTLL(long long int n){return __builtin_popcountll(n);}
#endif
namespace XX
{
template<template<typename> class Compare, typename T>
inline T& UP(T& x, const T& y){if(Compare<T>()(y, x)) x = y; return x;}
template<typename Compare, typename T>
inline T& UP(T& x, const T& y, Compare comp){if(comp(y, x)) x = y; return x;}
template<typename T> inline T& GT(T& x, const T& y){return UP<std::greater>(x, y);}
template<typename T> inline T& LS(T& x, const T& y){return UP<std::less>(x, y);}
template<typename T>
struct Mapper
{
int operator[](const T& v) { int& ret = table[v]; if(!ret) rtable[ret = table.size()] = v; return ret - 1; }
template<typename... Args> int operator()(Args... args) { return (*this)[T(args...)]; }
T rev(int idx){return rtable[idx + 1];}
std::map<T, int> table;
std::map<int, T> rtable;
};
template<typename T, int S>
struct ReferenceArray
{
struct It {typename std::array<T*, S>::iterator it; T& operator*(){return **it;} void operator++(){it++;} bool operator!=(const It& other){return it != other.it;} };
int size()const{return _ptr.size();}
It begin()const{return {_ptr.begin()};}
It end()const{return {_ptr.end()};}
T& operator[](int idx)const{return *_ptr[idx];}
mutable std::array<T*, S> _ptr;
};
template<typename T, typename... Args>
ReferenceArray<T, sizeof...(Args) + 1> MAKEV(T& arg1, Args&... args) {return {&arg1, &args...};}
struct Range
{
struct It { int num, step; int operator*(){return num;} void operator++(){num += step;} bool operator!=(const It& other){return num != other.num;} };
Range(int ee):b(0),e(ee){}
Range(int bb, int ee):b(bb), e(ee){}
It begin(){return {b, (b < e? 1: -1)};}
It end(){return {e, 0};}
int b, e;
};
}
template<typename T> struct ScanfSpecifier{};
#define DEF(T,V) template<> struct ScanfSpecifier<T>{static constexpr const char* value = V;};
DEF(char*,"%s")DEF(int,"%d")DEF(double,"%lf")DEF(float,"%f")DEF(char,"%c")DEF(const char*,"%s")DEF(unsigned long,"%lu")DEF(unsigned int, "%u")
#ifdef _MSC_VER
DEF(long long int,"%I64d")
#else
DEF(long long int,"%lld")
#endif
#undef DEF
template<typename T> int RD(T& arg){return std::scanf(ScanfSpecifier<T>::value, &arg);}
template<int S> int RD(char (&arg)[S]){return std::scanf("%s", arg);}
int RD(char* arg){return std::scanf("%s", arg);}
template<> int RD<char>(char& arg){return std::scanf(" %c", &arg);}
template<typename T, typename... Args> int RD(T& arg1, Args&... args) {return RD(arg1) + RD(args...);}
template<typename T> T RD(){T ret; RD(ret); return ret;}
template<typename It> void RDV(It begin, It end) { while(begin != end) RD(*begin++); }
template<typename C> void RDV(C& c) {RDV(std::begin(c), std::end(c));}
template<typename... Args> void WT(Args... args) { int alc = 0; int dummy[] = {((alc++? std::printf(" "): 0), std::printf(ScanfSpecifier<Args>::value, args), 0)...}; }
template<typename... Args> void WTL(Args... args) { WT(args...); std::printf("\n"); }
template<typename It> void WTV(It begin, It end) { int alc = 0; while(begin != end) (alc++? std::printf(" "): 0), WT(*begin++); }
template<typename C> void WTV(const C& c) {WTV(std::begin(c), std::end(c));}
template<typename It> void WTVL(It begin, It end) { WTV(begin, end); std::printf("\n"); }
template<typename C> void WTVL(const C& c) {WTVL(std::begin(c), std::end(c));}
namespace XX
{
template<typename... EdgeTs>
class Graph
{
public:
struct Edge: public EdgeTs...
{
int from, to;
Edge(int f, int t, EdgeTs... args) :from(f), to(t), EdgeTs(args)... {}
Edge(){}
};
struct Node:public Edge, BlockAllocater<Node>
{
Node* next;
template<typename... Args> Node(Node* nn, Args... args) :next(nn),Edge(args...) {}
};
typedef Node* EdgeIdx;
private:
std::vector<Node*> _adj;
int _numVertex;
void _dealloc(Node* node) { if(node) { _dealloc(node->next); delete node; } }
public:
Graph(int v = 0) :_adj(v) {}
//~Graph(){for(Node* node: _adj)_dealloc(node);}
int size(){return _adj.size();}
void resize(int size){_adj.resize(size);}
EdgeIdx add(int from, int to, EdgeTs... args) { return _adj[from] = new Node{_adj[from], from, to, args...}; }
Node& operator[](EdgeIdx idx){return idx->e;}
struct Enumerator
{
struct It
{
Node* ptr;
Node& operator*(){return *ptr;}
void operator++(){ptr = ptr->next;}
bool operator!=(const It& other){return ptr != other.ptr;}
}b, e;
It begin(){return b;}
It end(){return e;}
};
struct AllEnumerator
{
struct It
{
Node* ptr;
int v;
Graph& g;
Node& operator*(){return *ptr;}
void operator++()
{
ptr = ptr->next;
while(!ptr && ++v < g.size())
ptr = g._adj[v];
}
bool operator!=(const It& other){return ptr != other.ptr;}
};
Graph& g;
It begin()
{
for(int i = 0; i < g.size(); i++)
if(g._adj[i])
return {g._adj[i], i, g};
return end();
}
It end(){return {nullptr, 0, g};}
};
Enumerator adj(int v) { return {_adj[v], nullptr}; }
Enumerator adj(EdgeIdx idx) { return {idx, nullptr}; }
AllEnumerator edges() { return {*this}; }
Enumerator operator[](int idx){return adj(idx);}
};
}
namespace XX
{
template<typename... EdgeTs>
std::vector<int> topologicalsort(Graph<EdgeTs...>& g)
{
std::vector<int> deg(g.size());
for(auto& e: g.edges())
deg[e.to]++;
std::vector<int> ret(deg.size());
unsigned len = 0;
std::queue<int> que;
for(unsigned i = 0; i < deg.size(); i++)
if(deg[i] == 0)
que.push(i);
while(que.size())
{
int u = que.front();
que.pop();
ret[len++] = u;
for(auto& e: g[u])
if(--deg[e.to] == 0)
que.push(e.to);
}
if(len < ret.size())
ret.resize(len);
return ret;
}
}
//alias
using XX::Graph;
using XX::topologicalsort;
//RD[L],RDV[L],WT[L],WTV[L] for i/o
template<typename T> T& UMAX(T& x, T y){return XX::UP<std::greater>(x, y);}
template<typename T> T& UMIN(T& x, T y){return XX::UP<std::less>(x, y);}
using XX::UP; //(x,y) comp
using RG = XX::Range;
using XX::MAKEV;
using XX::Mapper;
//template
#include <vector>
#include <string>
#include <set>
#include <map>
#include <cstdlib>
#include <algorithm>
#include <functional>
#include <cstring>
using namespace std;
//alias
//bit operation => CLZ,CTZ,POPCNT
const int SQ = 384;
const int SL = (SQ + 63) / 64;
struct Req
{
int idx;
int t, u, x;
bool operator<(const Req& r)const{return x < r.x;}
}qs[SQ], qs2[SQ];
typedef unsigned long long int ull;
int value[100009];
int op[100009];
ull mask[100009][SL];
ull mask2[100009][SL];
ull mask3[SQ][SL];
void setb(ull mask[], int idx)
{
mask[idx >> 6] |= (1ull << (idx & 63));
}
bool test(ull mask[], int idx)
{
return mask[idx >> 6] & (1ull << (idx & 63));
}
void orb(ull m1[], ull m2[])
{
for(int i = 0; i < SL; i++)
m1[i] = m1[i] | m2[i];
}
void andb(ull m1[], ull m2[])
{
for(int i = 0; i < SL; i++)
m1[i] = m1[i] & m2[i];
}
int mn(ull m1[])
{
for(int i = 0; i < SL; i++)
if(m1[i])
return i * 64 + CTZLL(m1[i]);
return -1;
}
int main()
{
int N, M, Q;
RD(N, M, Q);
Graph<> g(N);
while(M--)
{
int u, v;
RD(u, v);
u--, v--;
g.add(u, v);
}
auto topo = topologicalsort(g);
if((int)topo.size() != N)
return -1;
for(int i = 0; i < Q; i += SQ)
{
memset(op, -1, sizeof(op));
memset(mask, 0, sizeof(mask));
memset(mask2, 0, sizeof(mask2));
memset(mask3, 0, sizeof(mask3));
int total = min(i + SQ, Q) - i;
for(int j = 0; j < total; j++)
{
RD(qs[j].t, qs[j].u);
qs[j].u--;
if(qs[j].t != 3)
{
setb(mask[qs[j].u], j);
RD(qs[j].x);
}
if(qs[j].t == 1)
op[qs[j].u] = j;
qs[j].idx = j;
qs2[j] = qs[j];
}
sort(qs2, qs2 + total);
for(int j = 0; j < total; j++)
if(qs2[j].t == 2)
setb(mask2[qs2[j].u], j);
for(int k = 0; k < N; k++)
{
int j = topo[k];
for(auto e: g[j])
{
orb(mask[e.to], mask[j]);
orb(mask2[e.to], mask2[j]);
if(op[j] != -1 && (op[e.to] == -1 || op[e.to] < op[j]))
op[e.to] = op[j];
}
}
for(int j = 0; j < total; j++)
if(qs[j].t == 3)
{
int u = qs[j].u;
int v = value[qs[j].u];
for(int k = 0; k < j; k++)
if(test(mask[u], k))
{
// WTL("?", j, k);
if(qs[k].t == 1 || v > qs[k].x)
v = qs[k].x;
}
WTL(v);
}
else if(qs[j].t == 1)
{
for(int k = 0; k < total; k++)
if(qs2[k].t == 2 && qs2[k].idx > j && qs2[k].x < qs[j].x)
setb(mask3[j], k);
}
for(int j = 0; j < N; j++)
{
if(op[j] != -1)
{
andb(mask2[j], mask3[op[j]]);
value[j] = qs[op[j]].x;
}
int idx = mn(mask2[j]);
if(idx != -1 && value[j] > qs2[idx].x)
value[j] = qs2[idx].x;
}
}
}
Java DAG Queries HackerRank 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();
}
}
Python 3 DAG Queries HackerRank Solution
from functools import reduce
def readVec():
return tuple(int(it) for it in input().split())
n, m, q = readVec()
vertexes = [0 for it in range(n+1)]
edges = {it : set() for it in range(n+1)}
for it in range(m):
a, b = readVec()
edges[a] |= {b}
def memoize(f):
cache = {}
def ret(n):
if n not in cache:
cache[n] = f(n)
return cache[n]
return ret
@memoize
def reachable(n):
return reduce(lambda x, y: x | y, (reachable(it) for it in edges[n]), {n})
for it in range(q):
query = readVec()
if query[0] == 1:
for it in reachable(query[1]):
vertexes[it] = query[2]
elif query[0] == 2:
for it in reachable(query[1]):
vertexes[it] = min(vertexes[it], query[2])
elif query[0] == 3:
print(vertexes[query[1]])
Python 2 DAG Queries HackerRank Solution
def neighbors(u):
return graph.get(u, [])
def add_neighbor(u, v):
nbs = neighbors(u)
nbs.append(v)
graph[u] = nbs
cache = {}
def reachable_nodes(u):
if u in cache:
return cache[u]
nodes = [u]
queue = [u]
visited = set([u])
while queue:
current = queue.pop(0)
for neighbor in neighbors(current):
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
nodes.append(neighbor)
cache[u] = nodes
return nodes
def query_1(u, x):
nodes = reachable_nodes(u)
for v in nodes:
values[v - 1] = x
def query_2(u, x):
nodes = reachable_nodes(u)
for v in nodes:
if values[v - 1] > x:
values[v - 1] = x
def query_3(u):
print values[u - 1]
n, m, q = map(int, raw_input().strip().split())
graph = {}
values = [0]*n
for _ in xrange(m):
u, v = map(int, raw_input().strip().split())
add_neighbor(u, v)
# print graph
# for i in range(1, n + 1):
# print i,"->",reachable_nodes(i)
for _ in xrange(q):
query = map(int, raw_input().split())
query_number = query[0]
if query_number == 1:
query_1(query[1], query[2])
elif query_number == 2:
query_2(query[1], query[2])
else:
query_3(query[1])
Leave a comment below
