Table of Contents
Going to the Office – 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++ Going to the Office HackerRank Solution
#include <queue>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <string.h>
#include <cassert>
using namespace std;
#define rep(i,a,b) for(__typeof(a) i=(a);i<(b);i++)
#define ll long long int
#define ii pair<int,int>
#define CLEAR(x,val) memset(x,val,sizeof(x))
#define SZ(v) (v).size()
#define MAX 100009
#define inf 1e9
/******** Data Structure ************/
int dist[2][MAX];
int pre [2][MAX];
vector< vector<int> > vv(MAX) , cost(MAX);
vector< vector<int> > tr(MAX) , trc(MAX);
/********* ititialize **************/
void reset() {
rep( i , 0 , 2 ) rep( j , 0 , MAX ) dist[i][j] = inf;
CLEAR( pre , -1 );
rep( i , 0 , MAX ) vv[i].clear() , cost[i].clear();
rep( i , 0 , MAX ) tr[i].clear() , trc[i].clear();
}
/********Dijkstra *****************/
void DIJ( int src , int id ) {
rep( i , 0 , MAX ) dist[id][i] = inf;
dist[id][src] = 0;
priority_queue< ii , vector<ii> , greater<ii> > Q;
ii tmp = make_pair( 0 , src );
Q.push(tmp);
while( !Q.empty() ) {
tmp = Q.top();Q.pop();
int w = tmp.first , u = tmp.second;
int sz = vv[u].size();
rep( i , 0 , sz ) {
int v = vv[u][i] , cst = cost[u][i];
if( dist[id][v] > w+cst ) {
dist[id][v] = w + cst;
pre[id][v] = u;
ii newp = make_pair( dist[id][v] , v );
Q.push(newp);
}
}
}
}
/*****Data structure for Query part ***********/
typedef struct edge {
int u , v , w;
bool friend operator < ( const edge &A , const edge &B ) {
return A.w > B.w;
}
}edge;
edge array[MAX];
priority_queue< edge > Heap[MAX];
int label[MAX] , minl[MAX] , maxl[MAX];
int counter;
/********* tree labeling **********************/
void DFS( int src ) {
int sz = tr[src].size();minl[src] = counter;
rep( i , 0 , sz ) {
int v = tr[src][i];
DFS( v );
}
label[src] = counter;
maxl[src] = counter;
counter++;
}
/*****MMG Algorithm****************************/
void replace( int src ) {
int sz = tr[src].size();
rep( i , 0 , sz ) {
int v = tr[src][i];
replace( v );
while(!Heap[v].empty()) {
Heap[src].push(Heap[v].top());Heap[v].pop();
}
}
while(!Heap[src].empty()) {
edge e = Heap[src].top();Heap[src].pop();
int u = e.u , v = e.v , w = e.w;
if( (label[u] >= minl[src] && label[u] <= maxl[src] ) && !(label[v] >= minl[src] && label[v] <= maxl[src] ) ) {
array[src] = e;Heap[src].push(e);break;
}
else if(!(label[u] >= minl[src] && label[u] <= maxl[src] ) && (label[v] >= minl[src] && label[v] <= maxl[src] )) {
array[src] = e;Heap[src].push(e);break;
}
}
}
int main()
{
reset();
int n , m;
scanf("%d %d" , &n , &m);
assert( n < 200000 && m < 200000 && n > 0 && m > 0 );
rep( i , 0 , m ) {
int u , v , w;scanf("%d %d %d" , &u , &v , &w );
assert( u >= 0 && u < n );assert( v >= 0 && v < n );assert( u != v );
assert( w <= 1000 );
vv[u].push_back(v);cost[u].push_back(w);
vv[v].push_back(u);cost[v].push_back(w);
}
int S , T;
scanf("%d %d" , &S , &T );
assert( S >= 0 && S < n );assert( T >= 0 && T < n );
DIJ( S , 0 );
DIJ( T , 1 );
map<ii,int> mp;mp.clear();
rep( i , 0 , n ) {
if( pre[0][i] != -1 ) {
tr[pre[0][i]].push_back(i);
mp[make_pair( i , pre[0][i])] = 1;
mp[make_pair( pre[0][i] , i)] = 1;
}
}
// After shortest path
counter = 1;
DFS( S );
/* DFS labeling for fining cut
rep( i , 0 , n ) {
cout << label[i] <<" " << minl[i] << " " << maxl[i] << "\n";
}
*/
rep( i , 0 , n ) array[i].w = inf;
rep( i , 0 , n ) {
int sz = vv[i].size();
rep( j , 0 , sz ) {
int v = vv[i][j] , w = cost[i][j];
if( !mp[make_pair( i ,v )] ) {
edge e = (edge){ i , v , dist[0][i]+w+dist[1][v] };
Heap[v].push(e);
}
}
}
replace(S);
// Query Part
mp.clear();
rep( i , 0 , n ) {
if( i != S ) {
mp[ make_pair(pre[0][i] , i ) ] = array[i].w;
mp[ make_pair(i , pre[0][i] ) ] = array[i].w;
}
}
int Q;scanf("%d" , &Q);
assert( Q < 200000 && Q > 0 );
map< ii , int > mp1;
int cur = T;
//
int tcnt = 0;
while( cur != -1 ) {
mp1[make_pair(pre[0][cur] , cur )] = mp[make_pair(pre[0][cur] , cur )];
mp1[make_pair(cur , pre[0][cur] )] = mp[make_pair(cur , pre[0][cur] )];
cur = pre[0][cur];
}
mp.clear();
rep( i , 0 , Q ) {
int u , v;
scanf("%d %d" , &u , &v );
assert( u >= 0 && u < n );assert( v >= 0 && v < n );assert( u != v );
if( mp1[make_pair( u , v ) ] == 0 ) cout << dist[0][T] << "\n";
else if( mp1[make_pair(u,v)] == inf ) cout << "Infinty\n";
else cout << mp1[make_pair( u , v ) ] <<"\n";
}
return 0;
}
Java Going to the Office HackerRank Solution
import java.util.*;
import static java.lang.Math.*;
import java.io.*;
public class Solution {
static class Foo47 {
/*
* after 2 dijkstra's parse, each node has 2 shortest path values from src and dest
* then from one shortest path tree, traverse the edges on shortest path from src to dest,
* while doing this, removing or adding edges cross the cut, and update the balanced bst
* each edge will be processed once, so this step will be O(nlgn) which will run in time
*/
static class Edge {
int i;
int j;
public boolean equals(Object obj) {
if (this == obj) return true;
if (obj instanceof Edge) {
Edge b = (Edge)obj;
return i == b.i && j == b.j;
}
return false;
}
public int hashCode() {
return i*31 + j;
}
public String toString() {
return "[" + i + ", " + j + "]";
}
public Edge(int i, int j) {
this.i = i;
this.j = j;
}
}
static class Shortest implements Comparable<Shortest> {
long dist;
int i;
int j;
public int compareTo(Shortest b) {
if (dist != b.dist) return dist - b.dist < 0 ? -1 : 1;
if (i != b.i) return i - b.i;
return j - b.j;
}
public String toString() {
return "[" + dist + ": " + i + ", " + j + "]";
}
public Shortest(int i, int j, long dist) {
this.i = i;
this.j = j;
this.dist = dist;
}
}
static class TreeNode {
int i;
int parent;
HashSet<TreeNode> child = new HashSet<TreeNode>();
public String toString() {
return "" + i + ": " + child;
}
}
static long INF = Long.MAX_VALUE/3;
int N;
TreeMap<Integer, Long>[] graph;
long[] distSrc;
long[] distDest;
ArrayList<Integer> path = new ArrayList<Integer>();
boolean reachable = true;
HashMap<Edge, Long> removeMap = new HashMap<Edge, Long>();
void main() {
BufferedReader br = null;
try {
br = new BufferedReader(new InputStreamReader(System.in));
String[] s = br.readLine().split(" ");
N = Integer.parseInt(s[0].trim());
int M = Integer.parseInt(s[1].trim());
long t = System.currentTimeMillis();
graph = new TreeMap[N];
for (int i = 0; i < N; i++) {
graph[i] = new TreeMap<Integer, Long>();
}
distSrc = new long[N];
distDest = new long[N];
for (int i = 0; i < M; i++) {
s = br.readLine().split(" ");
int u = Integer.parseInt(s[0].trim());
int v = Integer.parseInt(s[1].trim());
long wei = Long.parseLong(s[2].trim());
graph[u].put(v, wei);
graph[v].put(u, wei);
}
s = br.readLine().split(" ");
int src = Integer.parseInt(s[0].trim());
int dest = Integer.parseInt(s[1].trim());
foo(src, dest);
int Q = Integer.parseInt(br.readLine());
for (int i = 0; i < Q; i++) {
s = br.readLine().split(" ");
int u = Integer.parseInt(s[0].trim());
int v = Integer.parseInt(s[1].trim());
long dist = getDist(u, v, dest);
System.out.println(dist >= INF ? "Infinity" : dist);
}
//System.out.println(System.currentTimeMillis() - t);
} catch (Exception e) {
e.printStackTrace();
} finally {
try {
br.close();
} catch (Exception e) {
e.printStackTrace();
}
}
}
long getDist(int u, int v, int dest) {
int i = min(u, v);
int j = max(u, v);
Long dis = removeMap.get(new Edge(i, j));
if (dis == null)
return distSrc[dest];
return dis;
}
void foo(int src, int dest) {
distSrc = new long[N];
distDest = new long[N];
TreeNode root = dijkstra(true, src, dest, distSrc);
dijkstra(false, dest, src, distDest);
if (path.get(0) != src) {
reachable = false;
return;
}
HashSet<Integer> left = new HashSet<Integer>();
HashSet<Integer> right = new HashSet<Integer>();
for (int i = 0; i < N; i++)
right.add(i);
TreeSet<Shortest> shortSet = new TreeSet<Shortest>();
TreeNode node = root;
for (int i = 0; i < path.size()-1; i++) {
int u = path.get(i);
int v = path.get(i+1);
HashSet<Integer> middle = new HashSet<Integer>();
fillMiddle(middle, right, node, v);
for (int start : middle) {
for (Map.Entry<Integer, Long> entry : graph[start].entrySet()) {
int end = entry.getKey();
long wei = entry.getValue();
if (u == start && v == end) continue;
if (u == start && node.parent == end) continue;
if (left.contains(end)) {
// need remove
long dist = wei + distSrc[end] + distDest[start];
if (dist >= INF)
continue;
shortSet.remove(new Shortest(min(start, end), max(start, end), dist));
} else if (right.contains(end)) {
// need add
long dist = wei + distSrc[start] + distDest[end];
if (dist >= INF)
continue;
shortSet.add(new Shortest(min(start, end), max(start, end), dist));
}
}
}
if (!shortSet.isEmpty()) {
removeMap.put(new Edge(min(u, v), max(u, v)), shortSet.first().dist);
} else {
removeMap.put(new Edge(min(u, v), max(u, v)), INF);
}
for (TreeNode val : node.child) {
if (val.i == v) {
node = val;
break;
}
}
// move middle to left
for (int val : middle) {
left.add(val);
}
}
}
void fillMiddle(HashSet<Integer> middle, HashSet<Integer> right, TreeNode node, int v) {
middle.add(node.i);
right.remove(node.i);
for (TreeNode val : node.child) {
if (val.i == node.parent || val.i == v) continue;
fillMiddle(middle, right, val, -1);
}
}
static class Node implements Comparable<Node>{
int i;
long dist;
int parent;
public int compareTo(Node b) {
if (dist != b.dist) return dist < b.dist? -1 : 1;
return i - b.i;
}
}
TreeNode dijkstra(boolean needTree, int src, int dest, long[] dist) {
Arrays.fill(dist, INF);
dist[src] = 0;
Node[] state = new Node[N];
TreeSet<Node> queue = new TreeSet<Node>();
for (int i = 0; i < N; i++) {
Node node = new Node();
state[i] = node;
node.i = i;
node.parent = -1;
node.dist = i == src ? 0 : INF;
queue.add(node);
}
while (!queue.isEmpty()) {
Node curr = queue.pollFirst();
if (curr.dist == INF)
break;
int u = curr.i;
dist[u] = curr.dist;
for (Map.Entry<Integer, Long> entry : graph[u].entrySet()) {
int v = entry.getKey();
long wei = entry.getValue();
if (dist[u] + wei < state[v].dist) {
queue.remove(state[v]);
state[v].dist = dist[u]+wei;
state[v].parent = u;
queue.add(state[v]);
}
}
}
if (!needTree) return null;
TreeNode[] tree = new TreeNode[N];
for (int i = 0; i < N; i++) {
TreeNode node = new TreeNode();
node.i = i;
node.parent = -1;
tree[i] = node;
}
for (int i = 0; i < N; i++) {
if (state[i].parent != -1) {
tree[i].parent = state[i].parent;
tree[state[i].parent].child.add(tree[i]);
}
}
// fill path
int curr = dest;
do {
path.add(curr);
curr = state[curr].parent;
} while (curr != -1);
Collections.reverse(path);
return tree[src];
}
}
public static void main(String[] args) {
Foo47 foo = new Foo47();
foo.main();
}
}
Python 2 Going to the Office HackerRank Solution
class Minimizer:
def __init__(self, lst):
self.lst = lst
self.len = len(lst)
self.tree = [range(0, self.len, 2)]
l = len(self.tree[-1])
while l > 1:
self.tree.append([])
for i in range(l / 2 + l % 2):
self.tree[-1].append(self.tree[-2][2 * i])
l = len(self.tree[-1])
def _min(self, a, b):
if self.lst[a][LEVEL] > self.lst[b][LEVEL]:
return a
if self.lst[a][LEVEL] < self.lst[b][LEVEL]:
return b
if self.lst[a][DISTANCE] is None:
return b
if self.lst[b][DISTANCE] is None:
return a
if self.lst[a][DISTANCE] <= self.lst[b][DISTANCE]:
return a
return b
def update(self, a):
if a % 2 == 0:
idx0, idx1 = a, a + 1
else:
idx0, idx1 = a - 1, a
up_idx = a / 2
if idx1 < self.len:
_m = self._min(idx0, idx1)
else:
_m = idx0
if _m == self.tree[0][up_idx] and _m != a:
return
else:
self.tree[0][up_idx] = _m
level = 0
level_idx = up_idx
while level < len(self.tree) - 1:
if level_idx % 2 == 0:
idx0, idx1 = level_idx, level_idx + 1
else:
idx0, idx1 = level_idx - 1, level_idx
up_idx = level_idx / 2
if idx1 < len(self.tree[level]):
_m = self._min(self.tree[level][idx0], self.tree[level][idx1])
else:
_m = self.tree[level][idx0]
if _m == self.tree[level + 1][up_idx] and _m != a:
break
else:
self.tree[level + 1][up_idx] = _m
level += 1
level_idx = up_idx
def get(self):
if len(self.tree[-1]) == 0:
if len(self.lst) == 0:
return None
else:
return 0
else:
return self.tree[-1][0]
class CMinimizer(Minimizer):
'''We get a list of cities indices, _min is different...'''
def _min(self, a, b):
if cities[self.lst[a]][LEVEL] > cities[self.lst[b]][LEVEL]:
return a
if cities[self.lst[a]][LEVEL] < cities[self.lst[b]][LEVEL]:
return b
if cities[self.lst[a]][DISTANCE] is None:
return b
if cities[self.lst[b]][DISTANCE] is None:
return a
if cities[self.lst[a]][DISTANCE] <= cities[self.lst[b]][DISTANCE]:
return a
return b
class DMinimizer(Minimizer):
def _min(self, a, b):
if cities[self.lst[a]][LEVEL] > cities[self.lst[b]][LEVEL]:
return a
if cities[self.lst[a]][LEVEL] < cities[self.lst[b]][LEVEL]:
return b
if cities[self.lst[a]][DISTANCE] is None:
return b
if cities[self.lst[b]][DISTANCE] is None:
return a
if cities[self.lst[a]][DISTANCE] - cities[self.lst[a]][BESTDISTANCE] <= cities[self.lst[b]][DISTANCE] - cities[self.lst[b]][BESTDISTANCE]:
return a
return b
n, m = tuple(map(int, raw_input().split()))
LEVEL, DISTANCE, PARENT, BESTDISTANCE, BESTNEXT, INCITIESIDX, OUTCITIESIDX = 0, 1, 2, 3, 4, 5, 6
cities = []
for i in range(n):
cities.append([0, None, None, None, None, None, None])
dijkstra_minimizer = Minimizer(cities)
matrix = []
roads = {}
for i in range(n):
matrix.append({})
for i in range(m):
u, v, w = tuple(map(int, raw_input().split()))
if u > v:
u, v = v, u
roads[(u, v)] = None
matrix[u][v] = w
matrix[v][u] = w
# read more input
s, d = tuple(map(int, raw_input().split()))
q = int(raw_input())
cities[s] = [1, 0, None, None, None, None, None]
dijkstra_minimizer.update(s)
# Dijkstra to find initial best way
act = s
while act != d:
for c in matrix[act]:
new = cities[act][DISTANCE] + matrix[act][c]
if (cities[c][DISTANCE] is None) or (cities[c][DISTANCE] > new):
cities[c] = [1, new, act, None, None, None, None]
dijkstra_minimizer.update(c)
mn = dijkstra_minimizer.get()
if cities[mn][DISTANCE] is None or cities[mn][LEVEL] == 0:
break
cities[mn][LEVEL] = 0
dijkstra_minimizer.update(mn)
act = mn
bestdistance = cities[d][DISTANCE]
if bestdistance is None:
for i in range(q):
raw_input()
print 'Infinity'
exit(0)
for r in roads:
roads[r] = bestdistance
# update cities whith best way information
act = d
while 1:
pt = cities[act][PARENT]
cities[act] = [1, None, None, cities[act][DISTANCE], cities[act][BESTNEXT], None, None]
if pt is None:
break
cities[pt][BESTNEXT] = act
if act < pt:
r = (act, pt)
else:
r = (pt, act)
roads[r] = 'Infinity'
act = pt
cities[s][LEVEL] = 0
cities[s][DISTANCE] = 0
# create minimizer lists
incities = []
outcities = []
incitiesidx = 0
outcitiesidx = 0
for idx, c in enumerate(cities):
if c[BESTDISTANCE] is None:
c[OUTCITIESIDX] = outcitiesidx
outcitiesidx += 1
outcities.append(idx)
c[DISTANCE] = None
c[LEVEL] = 0
else:
c[INCITIESIDX] = incitiesidx
incitiesidx += 1
incities.append(idx)
cmin = CMinimizer(outcities)
dmin = DMinimizer(incities)
# Modified Dijkstra to find solution
act = s
last = s
while last != d:
for c in matrix[act]:
new = cities[act][DISTANCE] + matrix[act][c]
if (cities[c][DISTANCE] is None) or (cities[c][DISTANCE] > new):
if cities[c][INCITIESIDX] is None:
cities[c][LEVEL] = 1
cities[c][DISTANCE] = new
cmin.update(cities[c][OUTCITIESIDX])
elif c != cities[act][BESTNEXT]:
cities[c][DISTANCE] = new
dmin.update(cities[c][INCITIESIDX])
g = cmin.get()
if g is not None:
mn = outcities[g]
if g is None or cities[mn][DISTANCE] is None or cities[mn][LEVEL] == 0:
nxt = cities[last][BESTNEXT]
ct = cities[incities[dmin.get()]]
if ct[DISTANCE] is not None and ct[LEVEL] == 1:
if last < nxt:
r = (last, nxt)
else:
r = (nxt, last)
roads[r] = bestdistance + ct[DISTANCE] - ct[BESTDISTANCE]
act = nxt
cities[act][LEVEL] = 0
cities[act][DISTANCE] = cities[act][BESTDISTANCE]
dmin.update(cities[act][INCITIESIDX])
last = nxt
continue
cities[mn][LEVEL] = 0
cmin.update(cities[mn][OUTCITIESIDX])
act = mn
for i in range(q):
u, v = tuple(map(int, raw_input().split()))
if v < u:
u, v = v, u
print roads[(u, v)]
C Going to the Office HackerRank Solution
#include <stdio.h>
#include <stdlib.h>
typedef struct{
int u;
long long w;
} node;
void sort_a(long long*a,int size);
void merge(long long*a,long long*left_a,long long*right_a,int left_size,int right_size);
void sort_a2(int*a,int*b,int size);
void merge2(int*a,int*left_a,int*right_a,int*b,int*left_b,int*right_b,int left_size,int right_size);
void sort_a3(int*a,int*b,int*c,int size);
void merge3(int*a,int*left_a,int*right_a,int*b,int*left_b,int*right_b,int*c,int*left_c,int*right_c,int left_size,int right_size);
void heap_insert(node *heap,node *elem,int *size,int *heap_list);
void heap_update(node *heap,node *elem,int *heap_list);
void heap_read(node *heap,int *size,int *heap_list,node *ans);
int get_i(long long*a,long long num,int size);
long long med(long long*a,int size);
void range_increment(int i,int j,long long val,long long*tree,int N);
long long query(int i,long long*tree,int N);
void DJ(int N,int M,int*u,int*v,int*w,int*v_right,int*list_index,int*left_index,int*right_index,int S,long long*d,int*bridge,int*island);
int main(){
int N,M,S,D,Q,x,y,p,f,b,i,j;
int *u,*v,*w,*v_right,*list_index,*left_index,*right_index,*bridge,*island;
long long *d_s,*d_d,*path,*bypass;
scanf("%d%d",&N,&M);
u=(int*)malloc(M*sizeof(int));
v=(int*)malloc(M*sizeof(int));
w=(int*)malloc(M*sizeof(int));
v_right=(int*)malloc(M*sizeof(int));
list_index=(int*)malloc(M*sizeof(int));
left_index=(int*)malloc(M*sizeof(int));
right_index=(int*)malloc(M*sizeof(int));
d_s=(long long*)malloc(N*sizeof(long long));
d_d=(long long*)malloc(N*sizeof(long long));
bridge=(int*)malloc(M*sizeof(int));
path=(long long*)malloc(M*sizeof(long long));
island=(int*)malloc(N*sizeof(int));
bypass=(long long*)malloc(M*3*sizeof(long long));
for(i=0;i<M;i++){
scanf("%d%d%d",u+i,v+i,w+i);
list_index[i]=i;
bridge[i]=0;
}
for(i=0;i<N;i++)
d_s[i]=d_d[i]=-1;
for(i=0;i<M*3;i++)
bypass[i]=-1;
sort_a3(u,v,w,M);
for(i=0;i<M;i++)
v_right[i]=v[i];
sort_a2(v_right,list_index,M);
for(i=0;i<M;i++){
if(i==0 || u[i]!=u[i-1])
left_index[u[i]]=i;
if(i==0 || v_right[i]!=v_right[i-1])
right_index[v_right[i]]=i;
}
scanf("%d%d%d",&S,&D,&Q);
f=0;
DJ(N,M,u,v,w,v_right,list_index,left_index,right_index,S,d_s,bridge,island);
DJ(N,M,u,v,w,v_right,list_index,left_index,right_index,D,d_d,bridge,island);
if(d_s[D]==-1)
f=1;
else{
for(i=0,p=0;i<M;i++)
if(d_s[u[i]]!=-1 && (d_s[u[i]]+d_d[v[i]]+w[i]==d_s[D] || d_s[v[i]]+d_d[u[i]]+w[i]==d_s[D])){
bridge[i]=1;
path[p]=(d_s[u[i]]>d_s[v[i]])?d_s[u[i]]:d_s[v[i]];
p++;
}
sort_a(path,p);
for(i=0,b=0;i<M;i++)
if(bridge[i]){
x=(d_s[u[i]]<d_s[v[i]])?d_s[u[i]]:d_s[v[i]];
y=(d_s[u[i]]<d_s[v[i]])?d_s[v[i]]:d_s[u[i]];
j=get_i(path,x,p);
if(path[j]==y && (j==p-1 || path[j+1]>y)){
bridge[i]=2;
b++;
}
}
for(i=0;i<N;i++)
d_s[i]=island[i]=-1;
DJ(N,M,u,v,w,v_right,list_index,left_index,right_index,S,d_s,bridge,island);
for(i=0;i<M;i++)
if(bridge[i]!=2){
x=(island[u[i]]>island[v[i]])?island[v[i]]:island[u[i]];
y=(island[u[i]]>island[v[i]])?island[u[i]]:island[v[i]];
j=(island[u[i]]>island[v[i]])?d_s[v[i]]+w[i]+d_d[u[i]]:d_s[u[i]]+w[i]+d_d[v[i]];
range_increment(x+1,y,j,bypass,b);
}
}
while(Q--){
scanf("%d%d",&x,&y);
if(f)
printf("Infinity\n");
else{
for(i=left_index[x];i>=0 && i<M && u[i]==x;i++)
if(v[i]==y)
if(bridge[i]==2)
if(query((island[u[i]]>island[v[i]])?island[v[i]]+1:island[u[i]]+1,bypass,b)==-1)
printf("Infinity\n");
else
printf("%lld\n",query((island[u[i]]>island[v[i]])?island[v[i]]+1:island[u[i]]+1,bypass,b));
else
printf("%lld\n",d_s[D]);
for(i=right_index[x];i>=0 && i<M && v_right[i]==x;i++)
if(u[list_index[i]]==y)
if(bridge[list_index[i]]==2)
if(query((island[u[list_index[i]]]>island[v[list_index[i]]])?island[v[list_index[i]]]+1:island[u[list_index[i]]]+1,bypass,b)==-1)
printf("Infinity\n");
else
printf("%lld\n",query((island[u[list_index[i]]]>island[v[list_index[i]]])?island[v[list_index[i]]]+1:island[u[list_index[i]]]+1,bypass,b));
else
printf("%lld\n",d_s[D]);
}
}
return 0;
}
void sort_a(long long*a,int size){
if (size < 2)
return;
int m = (size+1)/2,i;
long long *left_a,*right_a;
left_a=(long long*)malloc(m*sizeof(long long));
right_a=(long long*)malloc((size-m)*sizeof(long long));
for(i=0;i<m;i++)
left_a[i]=a[i];
for(i=0;i<size-m;i++)
right_a[i]=a[i+m];
sort_a(left_a,m);
sort_a(right_a,size-m);
merge(a,left_a,right_a,m,size-m);
free(left_a);
free(right_a);
return;
}
void merge(long long*a,long long*left_a,long long*right_a,int left_size,int right_size){
int i = 0, j = 0;
while (i < left_size|| j < right_size) {
if (i == left_size) {
a[i+j] = right_a[j];
j++;
} else if (j == right_size) {
a[i+j] = left_a[i];
i++;
} else if (left_a[i] <= right_a[j]) {
a[i+j] = left_a[i];
i++;
} else {
a[i+j] = right_a[j];
j++;
}
}
return;
}
void sort_a2(int*a,int*b,int size){
if (size < 2)
return;
int m = (size+1)/2,i;
int*left_a,*left_b,*right_a,*right_b;
left_a=(int*)malloc(m*sizeof(int));
right_a=(int*)malloc((size-m)*sizeof(int));
left_b=(int*)malloc(m*sizeof(int));
right_b=(int*)malloc((size-m)*sizeof(int));
for(i=0;i<m;i++){
left_a[i]=a[i];
left_b[i]=b[i];
}
for(i=0;i<size-m;i++){
right_a[i]=a[i+m];
right_b[i]=b[i+m];
}
sort_a2(left_a,left_b,m);
sort_a2(right_a,right_b,size-m);
merge2(a,left_a,right_a,b,left_b,right_b,m,size-m);
free(left_a);
free(right_a);
free(left_b);
free(right_b);
return;
}
void merge2(int*a,int*left_a,int*right_a,int*b,int*left_b,int*right_b,int left_size,int right_size){
int i = 0, j = 0;
while (i < left_size|| j < right_size) {
if (i == left_size) {
a[i+j] = right_a[j];
b[i+j] = right_b[j];
j++;
} else if (j == right_size) {
a[i+j] = left_a[i];
b[i+j] = left_b[i];
i++;
} else if (left_a[i] <= right_a[j]) {
a[i+j] = left_a[i];
b[i+j] = left_b[i];
i++;
} else {
a[i+j] = right_a[j];
b[i+j] = right_b[j];
j++;
}
}
return;
}
void sort_a3(int*a,int*b,int*c,int size){
if (size < 2)
return;
int m = (size+1)/2,i;
int *left_a,*left_b,*left_c,*right_a,*right_b,*right_c;
left_a=(int*)malloc(m*sizeof(int));
right_a=(int*)malloc((size-m)*sizeof(int));
left_b=(int*)malloc(m*sizeof(int));
right_b=(int*)malloc((size-m)*sizeof(int));
left_c=(int*)malloc(m*sizeof(int));
right_c=(int*)malloc((size-m)*sizeof(int));
for(i=0;i<m;i++){
left_a[i]=a[i];
left_b[i]=b[i];
left_c[i]=c[i];
}
for(i=0;i<size-m;i++){
right_a[i]=a[i+m];
right_b[i]=b[i+m];
right_c[i]=c[i+m];
}
sort_a3(left_a,left_b,left_c,m);
sort_a3(right_a,right_b,right_c,size-m);
merge3(a,left_a,right_a,b,left_b,right_b,c,left_c,right_c,m,size-m);
free(left_a);
free(right_a);
free(left_b);
free(right_b);
free(left_c);
free(right_c);
return;
}
void merge3(int*a,int*left_a,int*right_a,int*b,int*left_b,int*right_b,int*c,int*left_c,int*right_c,int left_size,int right_size){
int i = 0, j = 0;
while (i < left_size|| j < right_size) {
if (i == left_size) {
a[i+j] = right_a[j];
b[i+j] = right_b[j];
c[i+j] = right_c[j];
j++;
} else if (j == right_size) {
a[i+j] = left_a[i];
b[i+j] = left_b[i];
c[i+j] = left_c[i];
i++;
} else if (left_a[i] <= right_a[j]) {
a[i+j] = left_a[i];
b[i+j] = left_b[i];
c[i+j] = left_c[i];
i++;
} else {
a[i+j] = right_a[j];
b[i+j] = right_b[j];
c[i+j] = right_c[j];
j++;
}
}
return;
}
void heap_insert(node *heap,node *elem,int *size,int *heap_list){
(*size)++;
int index=(*size);
while(index>1 && elem->w<heap[index/2].w){
heap[index]=heap[index/2];
heap_list[heap[index].u]=index;
index/=2;
}
heap[index]=(*elem);
heap_list[elem->u]=index;
return;
}
void heap_update(node *heap,node *elem,int *heap_list){
int index=heap_list[elem->u];
while(index>1 && elem->w<heap[index/2].w){
heap[index]=heap[index/2];
heap_list[heap[index].u]=index;
index/=2;
}
heap[index]=(*elem);
heap_list[elem->u]=index;
return;
}
void heap_read(node *heap,int *size,int *heap_list,node *ans){
(*ans)=heap[1];
int index=1;
while(index*2<*size && heap[*size].w>heap[index*2].w || index*2+1<*size && heap[*size].w>heap[index*2+1].w){
index=(heap[index*2].w>heap[index*2+1].w)?index*2+1:index*2;
heap[index/2]=heap[index];
heap_list[heap[index].u]=index/2;
}
heap[index]=heap[*size];
heap_list[heap[index].u]=index;
(*size)--;
return;
}
int get_i(long long*a,long long num,int size){
if(size==0)
return 0;
if(num>=med(a,size))
return get_i(&a[(size+1)>>1],num,size>>1)+((size+1)>>1);
else
return get_i(a,num,(size-1)>>1);
}
long long med(long long*a,int size){
return a[(size-1)>>1];
}
void range_increment(int i,int j,long long val,long long*tree,int N){
for(i+=N,j+=N;i<=j;i=(i+1)/2,j=(j-1)/2){
if(i%2 && (tree[i]==-1 || tree[i]>val)) tree[i] = val;
if(j%2==0 && (tree[j]==-1 || tree[j]>val)) tree[j] = val;
}
return;
}
long long query(int i,long long*tree,int N){
long long ans=-1,j;
for(j = i + N; j; j /= 2)
if(ans==-1 || ans>tree[j] && tree[j]!=-1)
ans=tree[j];
return ans;
}
void DJ(int N,int M,int*u,int*v,int*w,int*v_right,int*list_index,int*left_index,int*right_index,int S,long long*d,int*bridge,int*island){
int i,next_solve,heap_size=0,*heap_list,island_num;
node elem,*heap;
heap=(node*)malloc(N*sizeof(node));
heap_list=(int*)malloc(N*sizeof(int));
d[S]=0;
island[S]=0;
next_solve=S;
while(1){
for(i=left_index[next_solve];i>=0 && i<M && u[i]==next_solve;i++)
if(d[v[i]]==-1 || d[v[i]]>d[next_solve]+w[i]){
elem.u=v[i];
elem.w=d[next_solve]+w[i];
if(d[v[i]]==-1)
heap_insert(heap,&elem,&heap_size,heap_list);
else
heap_update(heap,&elem,heap_list);
d[v[i]]=d[next_solve]+w[i];
if(bridge[i]==2)
island[v[i]]=island[next_solve]+1;
else
island[v[i]]=island[next_solve];
}
else if(d[v[i]]==d[next_solve]+w[i]){
if(bridge[i]==2)
island_num=island[next_solve]+1;
else
island_num=island[next_solve];
if(island[v[i]]>island_num)
island[v[i]]=island_num;
}
for(i=right_index[next_solve];i>=0 && i<M && v_right[i]==next_solve;i++)
if(d[u[list_index[i]]]==-1 || d[u[list_index[i]]]>d[next_solve]+w[list_index[i]]){
elem.u=u[list_index[i]];
elem.w=d[next_solve]+w[list_index[i]];
if(d[u[list_index[i]]]==-1)
heap_insert(heap,&elem,&heap_size,heap_list);
else
heap_update(heap,&elem,heap_list);
d[u[list_index[i]]]=d[next_solve]+w[list_index[i]];
if(bridge[list_index[i]]==2)
island[u[list_index[i]]]=island[next_solve]+1;
else
island[u[list_index[i]]]=island[next_solve];
}
else if(d[u[list_index[i]]]==d[next_solve]+w[list_index[i]]){
if(bridge[list_index[i]]==2)
island_num=island[next_solve]+1;
else
island_num=island[next_solve];
if(island[u[list_index[i]]]>island_num)
island[u[list_index[i]]]=island_num;
}
if(heap_size==0)
break;
heap_read(heap,&heap_size,heap_list,&elem);
next_solve=elem.u;
}
free(heap);
free(heap_list);
return;
}
Warmup
Implementation
Strings
Sorting
Search
Graph Theory
Greedy
Dynamic Programming
Constructive Algorithms
Bit Manipulation
Recursion
Game Theory
NP Complete
Debugging
Leave a comment below
