# HackerRank Network Administration problem solution

In this HackerRank Network administration problem solution For each network transformation in form 3 AB ai ou should output:

1. "No connection" if there is no path between the requested servers considering just the links controlled by ai.
2. "D security devices placed" where D is the number of security devices placed so far on the existing connection between the requested servers considering just the links controlled by ai.

## Problem solution in Python programming.

import sys
from ctypes import *
edges = {}

def flip(this):
this[6], this[0], this[1], this[3], this[4] = not this[6], this[1], this[0], this[4], this[3]

def trickleDown(this):
this[6] = False
if this[0] is not None:
flip(this[0])
if this[1] is not None:
flip(this[1])

def splay(this, node):
if this[6] is True: trickleDown(this)
p = this[2]
while p is not None and p is not node:
g = p[2]
if g is None or g is node:
if p[6] is True:
trickleDown(p)
trickleDown(this)
if p[0] is this:
pL, this[2], p[2] = this[1], g, this
this[1], p[0] = p, pL
if pL is not None:
pL[2] = p
p[5] = p[3]['devices'] + pL[5] if p[1] is None else p[3]['devices'] + pL[5] + p[4]['devices'] + p[1][5]
else:
p[5] = 0 if p[1] is None else p[4]['devices'] + p[1][5]
else:
pR, this[2], p[2] = this[0], g, this
this[0], p[1] = p, pR
if pR is not None:
pR[2] = p
p[5] = p[4]['devices'] + pR[5] if p[0] is None else p[3]['devices'] + p[0][5] + p[4]['devices'] + pR[5]
else:
p[5] = 0 if p[0] is None else p[3]['devices'] + p[0][5]
if g is not None:
if g[0] is p:
g[0] = this
else:
g[1] = this
else:
if g[6] is True: trickleDown(g)
if p[6] is True:
trickleDown(p)
trickleDown(this)
if g[0] is p:
if p[0] is this:
pL, gL, gg = this[1], p[1], g[2]
this[1], p[0], p[1], g[0] = p, pL, g, gL
this[2], p[2], g[2] = gg, this, p
if gL is not None:
gL[2] = g
g[5] = g[3]['devices'] + gL[5] if g[1] is None else g[3]['devices'] + gL[5] + g[4]['devices'] + g[1][5]
else:
g[5] = 0 if g[1] is None else g[4]['devices'] + g[1][5]
if pL is not None:
pL[2] = p
p[5] = p[3]['devices'] + pL[5] + p[4]['devices'] + p[1][5]
else:
p[5] = p[4]['devices'] + p[1][5]
else:
pR, gL, gg = this[0], this[1], g[2]
this[0], this[1], p[1], g[0] = p, g, pR, gL
this[2], p[2], g[2] = gg, this, this
if gL is not None:
gL[2] = g
g[5] = g[3]['devices'] + gL[5] if g[1] is None else g[3]['devices'] + gL[5] + g[4]['devices'] + g[1][5]
else:
g[5] = 0 if g[1] is None else g[4]['devices'] + g[1][5]
if pR is not None:
pR[2] = p
p[5] = p[4]['devices'] + pR[5] if p[0] is None else p[3]['devices'] + p[0][5] + p[4]['devices'] + pR[5]
else:
p[5] = 0 if p[0] is None else p[3]['devices'] + p[0][5]
else:
if p[1] is this:
pR, gR, gg = this[0], p[0], g[2]
this[0], p[0], p[1], g[1] = p, g, pR, gR
this[2], p[2], g[2] = gg, this, p
if gR is not None:
gR[2] = g
g[5] = g[4]['devices'] + gR[5] if g[0] is None else g[3]['devices'] + g[0][5] + g[4]['devices'] + gR[5]
else:
g[5] = 0 if g[0] is None else g[3]['devices'] + g[0][5]
if pR is not None:
pR[2] = p
p[5] = p[3]['devices'] + p[0][5] + p[4]['devices'] + pR[5]
else:
p[5] = p[3]['devices'] + p[0][5]
else:
gR, pL, gg = this[0], this[1], g[2]
this[0], this[1], p[0], g[1] = g, p, pL, gR
this[2], p[2], g[2] = gg, this, this
if gR is not None:
gR[2] = g
g[5] = g[4]['devices'] + gR[5] if g[0] is None else g[3]['devices'] + g[0][5] + g[4]['devices'] + gR[5]
else:
g[5] = 0 if g[0] is None else g[3]['devices'] + g[0][5]
if pL is not None:
pL[2] = p
p[5] = p[3]['devices'] + pL[5] if p[1] is None else p[3]['devices'] + pL[5] + p[4]['devices'] + p[1][5]
else:
p[5] = 0 if p[1] is None else p[4]['devices'] + p[1][5]
if gg is not None:
if gg[0] is g:
gg[0] = this
else:
gg[1] = this
p = this[2]
this[5] = 0 if this[0] is None else this[3]['devices'] + this[0][5]
if this[1] is not None:
this[5] += this[4]['devices'] + this[1][5]

def link(u, v, i, l, edge):
U, V = i[u], i[v]
if U[2] is not None: splay(U, None)
if V[2] is not U: splay(V, U)
if V[2] is None:
if U[1] is not None:
flip(U)
if U[6] is True: trickleDown(U)
if V[0] is not None:
flip(V)
if V[6] is True: trickleDown(V)
U[1], V[2] = V, U
U[4] = V[3] = edge
U[5] = edge['devices'] + U[1][5] if U[0] is None else U[3]['devices'] + U[0][5] + edge['devices'] + U[1][5]
l[u] += 1
l[v] += 1
return True
else:
return False

def main():
global edges
S, L, A, T = c_int(), c_int(), c_int(), c_int()
optint, aint, xint, uint, vint = c_int(), c_int(), c_int(), c_int(), c_int()
libc.scanf(b"%d%d%d%d", byref(S), byref(L), byref(A), byref(T))
S, L, A, T = S.value, L.value, A.value, T.value
aref, uref, vref, xref, optref = byref(aint), byref(uint), byref(vint), byref(xint), byref(optint)
S += 1
A += 1
idx, load = tuple(tuple([None, None, None, None, None, 0, False] for i in range(S)) for j in range(A)), tuple([0]*S for j in range(A))
for _ in range(L):
libc.scanf(b"%d%d%d", uref, vref, aref)
u, v, a = uint.value, vint.value, aint.value
edge = edges[(u, v)] = {'admin':a, 'devices':0}
for _ in range(T):
libc.scanf(b"%d%d%d%d", optref, uref, vref, xref)
opt, u, v, x = optint.value, uint.value, vint.value, xint.value
edge = edges[(u, v)] if (u, v) in edges else None
if opt == 3:
if idx[x][u] is None or idx[x][v] is None:
print('No connection')
else:
U, V = idx[x][u], idx[x][v]
if U[2] is not None: splay(U, None)
if V[2] is not U: splay(V, U)
if V[2] is None:
print('No connection')
elif U[0] is V:
print(str(U[3]['devices'] if V[1] is None else U[3]['devices'] + V[4]['devices'] + V[1][5]) + ' security devices placed')
else:
print(str(U[4]['devices'] if V[0] is None else U[4]['devices'] + V[3]['devices'] + V[0][5]) + ' security devices placed')
elif opt == 2:
diff = x - edge['devices']
edge['devices'] = x
if U[2] is V:
p = V
while p is not None:
p[5] += diff
p = p[2]
elif V[2] is U:
p = U
while p is not None:
p[5] += diff
p = p[2]
else:
if U[2] is not None: splay(U, None)
if V[2] is not U: splay(V, U)
else:
if edge is None:
else:
continue
print('Network redundancy')
else:
U, V = idx[a][u], idx[a][v]
if U[2] is not None: splay(U, None)
if V[2] is not None: splay(V, U)
if U[0] is V:
U[0] = None
U[5] = 0 if U[2] is None else U[4]['devices'] + U[1][5]
else:
U[1] = None
U[5] = 0 if U[0] is None else U[3]['devices'] + U[0][5]
V[2] = None
print('Assignment done')
f.close()

if __name__ == "__main__":
from os import _exit
sys.stderr = None
main()
_exit()

## Problem solution in Java Programming.

import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Comparator;
import java.util.InputMismatchException;

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

public void solve(int testNumber, InputReader in, PrintWriter out) {
int S = in.nextInt();
int L = in.nextInt();
int A = in.nextInt();
int T = in.nextInt();
byte[][] deg = new byte[A][S];
Info[] infos = new Info[L];

for (int i = 0; i < L; i++) {
int x = in.nextInt() - 1;
int y = in.nextInt() - 1;
int a = in.nextInt() - 1;

if (lct[a][x] == null) {
}

if (lct[a][y] == null) {
}

++deg[a][x];
++deg[a][y];
infos[i] = new Info(a, edgeNode, edge(x, y));
}

Arrays.sort(infos, new Comparator<Info>() {
public int compare(Info a, Info b) {
return Long.compare(a.edge, b.edge);
}
});

long[] edges = new long[L];

for (int i = 0; i < L; i++) {
edges[i] = infos[i].edge;
}

for (int i = 0; i < T; i++) {
int t = in.nextInt();
int a = in.nextInt() - 1;
int b = in.nextInt() - 1;

if (t == 1) {
int admin = in.nextInt() - 1;
long e = edge(a, b);
int index = Arrays.binarySearch(edges, e);
Info info = index < 0 ? null : infos[index];

out.println("Network redundancy");
} else {
out.println("Assignment done");

}

}

}
} else if (t == 2) {
int x = in.nextInt();
edge(a, b))].edgeNode;
} else {
int admin = in.nextInt() - 1;

out.println("No connection");
} else {
out.println(res + " security devices placed");
}
}
}
}

static long edge(int u, int v) {
return ((long) Math.min(u, v) << 32) + Math.max(u, v);
}

static class Info {
long edge;

this.edgeNode = edgeNode;
this.edge = edge;
}
}

static int queryOperation(int leftValue, int rightValue) {
return leftValue + rightValue;
}

static int getNeutralValue() {
return 0;
}

public static class Node {
int nodeValue;
int subTreeValue;
int size;
boolean revert;
Node left;
Node right;
Node parent;

Node(int value) {
nodeValue = value;
subTreeValue = value;
size = 1;
}

boolean isRoot() {
return parent == null
|| (parent.left != this && parent.right != this);
}

void push() {
if (revert) {
revert = false;
Node t = left;
left = right;
right = t;

if (left != null) {
left.revert = !left.revert;
}

if (right != null) {
right.revert = !right.revert;
}
}
}

void update() {
subTreeValue = queryOperation(
queryOperation(getSubTreeValue(left), nodeValue),
getSubTreeValue(right));
size = 1 + getSize(left) + getSize(right);
}
}

static int getSize(Node root) {
return root == null ? 0 : root.size;
}

static int getSubTreeValue(Node root) {
return root == null ? getNeutralValue() : root.subTreeValue;
}

static void connect(Node ch, Node p, Boolean isLeftChild) {
if (ch != null) {
ch.parent = p;
}

if (isLeftChild != null) {
if (isLeftChild) {
p.left = ch;
} else {
p.right = ch;
}
}
}

static void rotate(Node x) {
Node p = x.parent;
Node g = p.parent;
boolean isRootP = p.isRoot();
boolean leftChildX = (x == p.left);
connect(leftChildX ? x.right : x.left, p, leftChildX);
connect(p, x, !leftChildX);
connect(x, g, isRootP ? null : p == g.left);
p.update();
}

static void splay(Node x) {
while (!x.isRoot()) {
Node p = x.parent;
Node g = p.parent;

if (!p.isRoot()) {
g.push();
}

p.push();
x.push();

if (!p.isRoot()) {
rotate((x == p.left) == (p == g.left) ? p : x);
}

rotate(x);
}

x.push();
x.update();
}

static Node expose(Node x) {
Node last = null;

for (Node y = x; y != null; y = y.parent) {
splay(y);
y.left = last;
last = y;
}

splay(x);

return last;
}

public static void makeRoot(Node x) {
expose(x);
x.revert = !x.revert;
}

public static boolean connected(Node x, Node y) {
if (x == y) {
return true;
}

expose(x);
expose(y);

return x.parent != null;
}

public static void link(Node x, Node y) {
makeRoot(x);
x.parent = y;
}

public static void cut(Node x, Node y) {
makeRoot(x);
expose(y);
y.right.parent = null;
y.right = null;
}

public static int query(Node from, Node to) {
makeRoot(from);
expose(to);

return getSubTreeValue(to);
}

public static void modify(Node from, Node to, int delta) {
makeRoot(from);
expose(to);
to.nodeValue = delta;
}
}
}

final InputStream is;
final byte[] buf = new byte[1024];
int pos;
int size;

this.is = is;
}

public int nextInt() {

while (isWhitespace(c)) {
}

int sign = 1;

if (c == '-') {
sign = -1;
}

int res = 0;

do {
if (c < '0' || c > '9') {
throw new InputMismatchException();
}

res = res * 10 + c - '0';
} while (!isWhitespace(c));

return res * sign;
}

if (size == -1) {
throw new InputMismatchException();
}

if (pos >= size) {
pos = 0;

try {
} catch (IOException e) {
throw new InputMismatchException();
}

if (size <= 0) {
return -1;
}
}

return buf[pos++] & 255;
}

static boolean isWhitespace(int c) {
return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}
}

## Problem solution in C++ programming.

#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <cctype>
#include <cassert>
#include <limits>
#include <functional>
#include <bitset>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#if defined(_MSC_VER) || __cplusplus > 199711L
#define aut(r,v) auto r = (v)
#else
#define aut(r,v) typeof(v) r = (v)
#endif
#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
using namespace std;
typedef vector<int> vi; typedef pair<int,int> pii; typedef vector<pair<int,int> > vpii;
typedef long long ll; typedef vector<long long> vl; typedef pair<long long,long long> pll; typedef vector<pair<long long,long long> > vpll;
typedef vector<string> vs; typedef long double ld;
template<typename T, typename U> inline void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> inline void amax(T &x, U y) { if(x < y) x = y; }

unsigned xor128() {
static unsigned x = 123456789, y = 362436069, z = 521288629, w = 88675123;
unsigned t = x ^ (x << 11);
x = y; y = z; z = w;
return w = w ^ (w >> 19) ^ (t ^ (t >> 8));
}

template<typename Derived>
struct PNodeBase {
Derived *left, *right, *parent;
int size;
PNodeBase(): left(NULL), right(NULL), parent(NULL), size(1) { }
inline Derived *update() {
size = (!left ? 0 : left->size) + 1 + (!right ? 0 : right->size);
return derived();
}
inline void propagate() { }
if(left = c) c->parent = derived();
return derived()->update();
}
if(right = c) c->parent = derived();
return derived()->update();
}
inline Derived *linklr(Derived *l, Derived *r) {
if(left = l) l->parent = derived();
if(right = r) r->parent = derived();
return derived()->update();
}
static inline Derived *cut(Derived *t) {
if(t) t->parent = NULL;
return t;
}
private:
inline Derived *derived() { return static_cast<Derived*>(this); }
};
struct Node : PNodeBase<Node> {
typedef PNodeBase<Node> Base;
int weight, sum;
bool reversed;
Node(): weight(0), sum(0), reversed(false) { }
Node *update() {
sum = (!left ? 0 : left->sum) + weight + (!right ? 0 : right->sum);
return static_cast<Base*>(this)->update();
}
inline void propagate() {
if(reversed) {
swap(left, right);
if(left != 0) left->reversed ^= true;
if(right != 0) right->reversed ^= true;
reversed = false;
}
return static_cast<Base*>(this)->propagate();
}
};

struct PRBSTBase {
typedef Node *Ref;
static int size(Ref t) { return !t ? 0 : t->size; }
static Ref join(Ref l, Ref r) {
if(!l) return r;
if(!r) return l;
if((int)(xor128() % (l->size + r->size)) < l->size) {
l->propagate();
}else {
r->propagate();
}
}
typedef pair<Ref,Ref> RefPair;
static RefPair split(Ref t, int k) {
if(!t) return RefPair((Ref)NULL, (Ref)NULL);
t->propagate();
int s = size(t->left);
if(k <= s) {
RefPair p = split(Node::cut(t->left), k);
}else {
RefPair p = split(Node::cut(t->right), k - s - 1);
}
}
static Ref insert(Ref t, int k, Ref n) {
if(!t) return n;
if(xor128() % (t->size + 1) == 0) {
RefPair p = split(t, k);
}
t->propagate();
int s = size(t->left);
if(k <= s)
else
return t->linkr(insert(Node::cut(t->right), k - s - 1, n));
}
static RefPair remove(Ref t, int k) {
if(!t) return RefPair((Ref)NULL, (Ref)NULL);
t->propagate();
int s = size(t->left);
if(k < s) {
RefPair p = remove(Node::cut(t->left), k);
}else if(k > s) {
RefPair p = remove(Node::cut(t->right), k - s - 1);
}else {
Ref a = join(Node::cut(t->left), Node::cut(t->right));
}
}
static Ref index(Ref t, int k) {
if(!t) return NULL;
t->propagate();
int s = size(t->left);
if(k < s)
return index(t->left, k);
else if(k > s)
return index(t->right, k - s - 1);
else
return t;
}
static void topDown(Ref t) {
Ref nodes[128]; int k = 0;
for(Ref u = t; u != 0; u = u->parent)
nodes[k ++] = u;
while(k > 0)
nodes[-- k]->propagate();
}
static pair<Ref,int> findRoot(Ref t) {
if(!t) return make_pair((Ref)NULL, 0);
topDown(t);
int k = size(t->left);
while(true) {
Ref p = t->parent;
if(!p) return make_pair(t, k);
if(p->right == t)
k += size(p->left) + 1;
t = p;
}
}
};
typedef PRBSTBase BST;

struct Vector2 {
int a[2], s;
Vector2(): s(0) { }
int operator[](int i) const { assert(i < s); return a[i]; }
void push_back(int x) { a[s ++] = x; }
void erase(int x) { s = remove(a, a + s, x) - a; }
int size() const { return s; }
bool empty() const { return s == 0; }
};

void link(int i, int a, int x, int y, const vector<vector<Vector2> > &g, vector<Node> &nodes) {
Node *t = &nodes[i];
assert(BST::size(t) == 1);
if(!g[a][x].empty()) {
Node *l = &nodes[g[a][x][0]];
pair<Node*,int> pl = BST::findRoot(l);
if(pl.second != BST::size(pl.first) - 1) {
assert(pl.second == 0);
pl.first->reversed ^= true;
}
t = BST::join(pl.first, t);
}
if(!g[a][y].empty()) {
Node *r = &nodes[g[a][y][0]];
pair<Node*,int> pr = BST::findRoot(r);
if(pr.second != 0) {
assert(pr.second == BST::size(pr.first) - 1);
pr.first->reversed ^= true;
}
t = BST::join(t, pr.first);
}
}

int main() {
int S, L, AA, T;
scanf("%d%d%d%d", &S, &L, &AA, &T);
vector<vector<Vector2> > g(AA, vector<Vector2>(S));
vector<pii> edges(L);
vector<Node> nodes(L);
rep(i, L) {
int x, y, a;
scanf("%d%d%d", &x, &y, &a), -- x, -- y, -- a;
if(x > y) swap(x, y);

link(i, a, x, y, g, nodes);

g[a][x].push_back(i);
g[a][y].push_back(i);

edges[i] = mp(x, y);
}
const char *msgs[9] = {
"?????\n",
"Network redundancy\n",
"Assignment done\n",
"",
"No connection\n",
"%d security devices placed\n",
};
rep(ii, T) {
int ty, A, B, x, a;
scanf("%d%d%d%d", &ty, &A, &B, &x), -- A, -- B;
a = x - 1;
if(A > B) swap(A, B);

int result; int ans = -1;
if(ty == 1) {
result = 1;
result = 2;
}else if(g[a][A].size() >= 2 || g[a][B].size() >= 2) {
result = 3;
}else {
int i = it->second, pa = admin[i];
Node *tt = &nodes[i];
pair<Node*,int> p = BST::findRoot(tt);
Node *t = p.first;

{
Node *l = g[a][A].empty() ? 0 : BST::findRoot(&nodes[g[a][A][0]]).first;
Node *r = g[a][B].empty() ? 0 : BST::findRoot(&nodes[g[a][B][0]]).first;
if(l != 0 && r != 0 && l == r) {
result = 4;
goto next;
}
}

if(p.second != 0) {
int j = BST::index(p.first, p.second - 1) - &nodes[0];
p.first = BST::split(p.first, p.second).second;
p.second = 0;
}
}
if(p.second != BST::size(p.first) - 1) {
int j = BST::index(p.first, p.second + 1) - &nodes[0];
p.first = BST::split(p.first, p.second + 1).first;
}
}
g[pa][A].erase(i);
g[pa][B].erase(i);

link(i, a, A, B, g, nodes);

g[a][A].push_back(i);
g[a][B].push_back(i);

result = 5;
}
}else if(ty == 2) {
Node *tt = &nodes[i];
pair<Node*,int> p = BST::findRoot(tt);
Node *u = BST::remove(p.first, p.second).first;
tt->weight = x;
tt->update();
BST::insert(u, p.second, tt);
result = 6;
}else if(ty == 3) {
if(A == B) {
result = 8, ans = 0;
goto next;
}
if(g[a][A].empty() || g[a][B].empty()) {
result = 7;
goto next;
}
Node *l = &nodes[g[a][A][0]];
Node *r = &nodes[g[a][B][0]];
pair<Node*,int> pl = BST::findRoot(l);
pair<Node*,int> pr = BST::findRoot(r);
if(pl.first != pr.first) {
result = 7;
goto next;
}
if(g[a][A].size() == 2) {
Node *l1 = &nodes[g[a][A][1]];
pair<Node*,int> pl1 = BST::findRoot(l1);
if(pl1.first != pl.first) abort();
if(abs(pl.second - pr.second) > abs(pl1.second - pr.second))
l = l1, pl = pl1;
}
if(g[a][B].size() == 2) {
Node *r1 = &nodes[g[a][B][1]];
pair<Node*,int> pr1 = BST::findRoot(r1);
if(pr1.first != pr.first) abort();
if(abs(pl.second - pr.second) > abs(pl.second - pr1.second))
r = r1, pr = pr1;
}
Node *t = pl.first;
int L = pl.second, R = pr.second;
if(L > R) swap(L, R);
pair<Node*,Node*> p = BST::split(t, R + 1);
pair<Node*,Node*> q = BST::split(p.first, L);

Node *u = q.second;
result = 8;
ans = u->sum;

t = BST::join(BST::join(q.first, q.second), p.second);
}
next:;
printf(msgs[result], ans);
}
return 0;
}

## Problem solution in C programming.

#include <stdio.h>
#include <stdlib.h>
#define HASH_SIZE 123455
typedef struct _ct_node{
int x;
int y;
int size;
int priority;
int a;
int value;
int sum;
int reverse;
struct _ct_node *left,*right,*parent,*next;
} ct_node;
void find(ct_node *p,int *idx,ct_node **ret);
void insert(ct_node *p);
ct_node* search(int x,int y);
ct_node* merge(ct_node *L,ct_node *R);
int sizeOf(ct_node *root);
int sumOf(ct_node *root);
void recalc(ct_node *root);
void split(int x,ct_node **L,ct_node **R,ct_node *root);
int sum(ct_node *p,int x,int y);
void push(ct_node *root);
ct_node *a[100000][100][2],*hash[HASH_SIZE];

int main(){
int S,L,A,T,x,y,z,w,i;
ct_node *p;
scanf("%d%d%d%d",&S,&L,&A,&T);
for(i=0;i<L;i++){
scanf("%d%d%d",&x,&y,&z);
x--;
y--;
z--;
p=(ct_node*)malloc(sizeof(ct_node));
p->x=x;
p->y=y;
p->size=1;
p->priority=rand();
p->a=z;
p->value=p->sum=p->reverse=0;
p->left=p->right=p->parent=p->next=NULL;
insert(p);
}
while(T--){
scanf("%d%d%d%d",&w,&x,&y,&z);
if(w==1){
p=search(x-1,y-1);
if(!p)
p=search(y-1,x-1);
if(!p)
else if(p->a==z-1)
else if(a[x-1][z-1][1] || a[y-1][z-1][1])
else{
w=p->a;
printf("Network redundancy\n");
}
else
printf("Assignment done\n");
}
}
else if(w==2){
p=search(x-1,y-1);
if(p)
else
}
else{
if(x==y){
printf("No connection\n");
continue;
}
if(w==-1)
printf("No connection\n");
else
printf("%d security devices placed\n",w);
}
}
return 0;
}
int ret,idx1,idx2,idx3,idx4;
ct_node *p1,*p2,*p3,*p4,*pp1,*pp2;
p1=a[x][z][0];
p2=a[x][z][1];
p3=a[y][z][0];
p4=a[y][z][1];
if(!p1 || !p3)
return -1;
find(p1,&idx1,&pp1);
find(p3,&idx3,&pp2);
idx2=idx4=-1;
if(p2)
find(p2,&idx2,&pp1);
if(p4)
find(p4,&idx4,&pp2);

/////////////////////
if(idx2!=-1 && !(idx1-idx2==1 || idx2-idx1==1)){
while(1);
printf("Oh no. %d %d\n",idx1,idx2);
}
if(idx4!=-1 && !(idx3-idx4==1 || idx4-idx3==1)){
while(1);
printf("Oh no. %d %d\n",idx3,idx4);
}
/////////////////////

if(pp1!=pp2)
return -1;
if(idx2==-1 && idx4==-1)
return pp1->sum;
if(idx1==idx3)
return sum(pp1,idx1,idx3);
else if(idx1<idx3)
if(idx2==-1)
if(idx3<idx4)
return sum(pp1,idx1,idx3);
else
return sum(pp1,idx1,idx4);
else if(idx4==-1)
if(idx1<idx2)
return sum(pp1,idx2,idx3);
else
return sum(pp1,idx1,idx3);
else
if(idx1<idx2)
if(idx3<idx4)
return sum(pp1,idx2,idx3);
else
return sum(pp1,idx2,idx4);
else
if(idx3<idx4)
return sum(pp1,idx1,idx3);
else
return sum(pp1,idx1,idx4);
else
if(idx2==-1)
if(idx3<idx4)
return sum(pp1,idx4,idx1);
else
return sum(pp1,idx3,idx1);
else if(idx4==-1)
if(idx1<idx2)
return sum(pp1,idx3,idx1);
else
return sum(pp1,idx3,idx2);
else
if(idx1<idx2)
if(idx3<idx4)
return sum(pp1,idx4,idx1);
else
return sum(pp1,idx3,idx1);
else
if(idx3<idx4)
return sum(pp1,idx4,idx2);
else
return sum(pp1,idx3,idx2);
return ret;
}
p->value=x;
recalc(p);
for(;p->parent;p=p->parent)
recalc(p->parent);
return;
}
int idx1,idx2;
ct_node *p1,*p2;
p->a=x;
if(!a[p->x][x][0] && !a[p->y][x][0]){
a[p->x][x][0]=p;
a[p->y][x][0]=p;
return 0;
}
else if(!a[p->x][x][0] && a[p->y][x][0]){
find(a[p->y][x][0],&idx1,&p1);
if(idx1)
merge(p1,p);
else
merge(p,p1);
a[p->x][x][0]=p;
a[p->y][x][1]=p;
return 0;
}
else if(a[p->x][x][0] && !a[p->y][x][0]){
find(a[p->x][x][0],&idx1,&p1);
if(idx1)
merge(p1,p);
else
merge(p,p1);
a[p->x][x][1]=p;
a[p->y][x][0]=p;
return 0;
}
find(a[p->x][x][0],&idx1,&p1);
find(a[p->y][x][0],&idx2,&p2);
if(p1==p2)
return 1;
if(!idx1 && !idx2){
p1->reverse^=1;
merge(p1,merge(p,p2));
}
else if(!idx1 && idx2)
merge(p2,merge(p,p1));
else if(idx1 && !idx2)
merge(p1,merge(p,p2));
else{
p2->reverse^=1;
merge(p1,merge(p,p2));
}
a[p->x][x][1]=p;
a[p->y][x][1]=p;
return 0;
}
int idx;
ct_node *p1,*p2;
find(p,&idx,&p1);
split(idx-1,&p1,&p2,p1);
split(0,&p1,&p2,p2);
if(a[p->x][p->a][0]==p)
a[p->x][p->a][0]=a[p->x][p->a][1];
if(a[p->y][p->a][0]==p)
a[p->y][p->a][0]=a[p->y][p->a][1];
a[p->x][p->a][1]=NULL;
a[p->y][p->a][1]=NULL;
return;
}
void find(ct_node *p,int *idx,ct_node **ret){
int d,i;
for(i=-1;p->parent;p=p->parent){
if(i==-1)
if(p->reverse)
i=sizeOf(p->right);
else
i=sizeOf(p->left);
else
if(!d && p->reverse)
i=sizeOf(p->right)+sizeOf(p->left)-i;
else if(d && !p->reverse)
i+=sizeOf(p->left)+1;
else if(d && p->reverse)
i=sizeOf(p->right)-i-1;
if(p->parent->left==p)
d=0;
else
d=1;
}
if(i==-1)
if(p->reverse)
i=sizeOf(p->right);
else
i=sizeOf(p->left);
else
if(!d && p->reverse)
i=sizeOf(p->right)+sizeOf(p->left)-i;
else if(d && !p->reverse)
i+=sizeOf(p->left)+1;
else if(d && p->reverse)
i=sizeOf(p->right)-i-1;
*idx=i;
*ret=p;
return;
}
void insert(ct_node *p){
int bucket=(p->x+100000LL*p->y)%HASH_SIZE;
p->next=hash[bucket];
hash[bucket]=p;
return;
}
ct_node* search(int x,int y){
int bucket=(x+100000LL*y)%HASH_SIZE;
ct_node *t=hash[bucket];
while(t){
if(t->x==x && t->y==y)
return t;
t=t->next;
}
return NULL;
}
ct_node* merge(ct_node *L,ct_node *R){
if(!L)
return R;
if(!R)
return L;
if(L->priority>R->priority){
push(L);
if(L->right)
L->right->parent=NULL;
L->right=merge(L->right,R);
if(L->right)
L->right->parent=L;
recalc(L);
return L;
}
push(R);
if(R->left)
R->left->parent=NULL;
R->left=merge(L,R->left);
if(R->left)
R->left->parent=R;
recalc(R);
return R;
}
int sizeOf(ct_node *root){
return (root)?root->size:0;
}
int sumOf(ct_node *root){
return (root)?root->sum:0;
}
void recalc(ct_node *root){
root->size=sizeOf(root->left)+sizeOf(root->right)+1;
root->sum=sumOf(root->left)+sumOf(root->right)+root->value;
return;
}
void split(int x,ct_node **L,ct_node **R,ct_node *root){
if(!root){
*L=*R=NULL;
return;
}
push(root);
int curIndex=sizeOf(root->left);
ct_node *t;
if(curIndex<=x){
if(root->right)
root->right->parent=NULL;
split(x-curIndex-1,&t,R,root->right);
if(t)
t->parent=root;
root->right=t;
recalc(root);
*L=root;
}
else{
if(root->left)
root->left->parent=NULL;
split(x,L,&t,root->left);
if(t)
t->parent=root;
root->left=t;
recalc(root);
*R=root;
}
return;
}
int sum(ct_node *p,int x,int y){
int ret;
ct_node *p1,*p2;
split(y,&p2,&p,p);
split(x-1,&p1,&p2,p2);
ret=p2->sum;
merge(p1,merge(p2,p));
return ret;
}
void push(ct_node *root){
if(!root || !root->reverse)
return;
ct_node *t=root->left;
root->left=root->right;
root->right=t;
root->reverse=0;
if(root->left)
root->left->reverse^=1;
if(root->right)
root->right->reverse^=1;
return;
}