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
    libc = cdll.LoadLibrary("libc.so.6")
    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}
        link(u, v, idx[a], load[a], edge)
    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:
            U, V = idx[edge['admin']][u], idx[edge['admin']][v]
            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:
                print('Wrong link')
            elif edge['admin'] == x:
                print('Already controlled link')
            else:
                if load[x][u] == 2 or load[x][v] == 2:
                    print('Server overload')
                    continue
                if link(u, v, idx[x], load[x], edge) is False:
                    print('Network redundancy')
                else:
                    a = edge['admin']
                    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
                    load[a][u] -= 1
                    load[a][v] -= 1
                    edge['admin'] = x
                    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 class Network_administration {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        NetworkAdministration solver = new NetworkAdministration();
        solver.solve(1, in, out);
        out.close();
    }
}

class NetworkAdministration {
    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();
        LinkCutTree.Node[][] lct = new LinkCutTree.Node[A][S];
        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;
            LinkCutTree.Node edgeNode = new LinkCutTree.Node(0);
            
            if (lct[a][x] == null) {
                lct[a][x] = new LinkCutTree.Node(0);
            }

            if (lct[a][y] == null) {
                lct[a][y] = new LinkCutTree.Node(0);
            }

            LinkCutTree.link(lct[a][x], edgeNode);
            LinkCutTree.link(lct[a][y], edgeNode);
            ++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];
                Integer prevAdmin = info == null ? null : info.admin;

                if (prevAdmin == null) {
                    out.println("Wrong link");
                } else if (prevAdmin == admin) {
                    out.println("Already controlled link");
                } else if (deg[admin][a] == 2 || deg[admin][b] == 2) {
                    out.println("Server overload");
                } else if (lct[admin][a] != null && lct[admin][b] != null
                        && LinkCutTree.connected(lct[admin][a], lct[admin][b])) {
                    out.println("Network redundancy");
                } else {
                    out.println("Assignment done");
                    --deg[prevAdmin][a];
                    --deg[prevAdmin][b];
                    ++deg[admin][a];
                    ++deg[admin][b];
                    LinkCutTree.Node edgeNode = info.edgeNode;
                    LinkCutTree.cut(lct[prevAdmin][a], edgeNode);
                    LinkCutTree.cut(lct[prevAdmin][b], edgeNode);

                    if (lct[admin][a] == null) {
                        lct[admin][a] = new LinkCutTree.Node(0);
                    }

                    if (lct[admin][b] == null) {
                        lct[admin][b] = new LinkCutTree.Node(0);
                    }

                    LinkCutTree.link(lct[admin][a], edgeNode);
                    LinkCutTree.link(lct[admin][b], edgeNode);
                    info.admin = admin;
                }
            } else if (t == 2) {
                int x = in.nextInt();
                LinkCutTree.Node edgeNode = infos[Arrays.binarySearch(edges,
                        edge(a, b))].edgeNode;
                LinkCutTree.modify(edgeNode, edgeNode, x);
            } else {
                int admin = in.nextInt() - 1;

                if (lct[admin][a] == null || lct[admin][b] == null
                        || !LinkCutTree.connected(lct[admin][a], lct[admin][b])) {
                    out.println("No connection");
                } else {
                    int res = LinkCutTree.query(lct[admin][a], lct[admin][b]);
                    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 {
        int admin;
        LinkCutTree.Node edgeNode;
        long edge;

        public Info(int admin, LinkCutTree.Node edgeNode, long edge) {
            this.admin = admin;
            this.edgeNode = edgeNode;
            this.edge = edge;
        }
    }

    static class LinkCutTree {
        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;
        }
    }
}

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

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

    public int nextInt() {
        int c = read();

        while (isWhitespace(c)) {
            c = read();
        }

        int sign = 1;

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

        int res = 0;

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

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

        return res * sign;
    }

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

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

            try {
                size = is.read(buf);
            } 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() { }
    inline Derived *linkl(Derived *c) {
        if(left = c) c->parent = derived();
        return derived()->update();
    }
    inline Derived *linkr(Derived *c) {
        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();
            return l->linkr(join(Node::cut(l->right), r));
        }else {
            r->propagate();
            return r->linkl(join(l, Node::cut(r->left)));
        }
    }
    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);
            return RefPair(p.first, t->linkl(p.second));
        }else {
            RefPair p = split(Node::cut(t->right), k - s - 1);
            return RefPair(t->linkr(p.first), p.second);
        }
    }
    static Ref insert(Ref t, int k, Ref n) {
        if(!t) return n;
        if(xor128() % (t->size + 1) == 0) {
            RefPair p = split(t, k);
            return n->linklr(p.first, p.second);
        }
        t->propagate();
        int s = size(t->left);
        if(k <= s)
            return t->linkl(insert(Node::cut(t->left), k, n));
        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);
            return RefPair(t->linkl(p.first), p.second);
        }else if(k > s) {
            RefPair p = remove(Node::cut(t->right), k - s - 1);
            return RefPair(t->linkr(p.first), p.second);
        }else {
            Ref a = join(Node::cut(t->left), Node::cut(t->right));
            return RefPair(a, t->linklr(NULL, NULL));
        }
    }
    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));
    map<pii,int> links;
    vector<pii> edges(L);
    vector<Node> nodes(L);
    vector<int> admin(L, -1);
    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);
        links[mp(x, y)] = i;
        admin[i] = a;
    }
    const char *msgs[9] = {
        "?????\n",
        "Wrong link\n",
        "Already controlled link\n",
        "Server overload\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) {
            auto it = links.find(mp(A, B));
            if(it == links.end()) {
                result = 1;
            }else if(admin[it->second] == a) {
                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;
                    }
                }

                //??admin?????????
                if(p.second != 0) {
                    int j = BST::index(p.first, p.second - 1) - &nodes[0];
                    if(admin[j] == pa) {
                        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];
                    if(admin[j] == pa) {
                        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);

                admin[i] = a;

                result = 5;
            }
        }else if(ty == 2) {
            if(!links.count(mp(A, B))) abort();
            int i = links[mp(A, B)];
            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;
int sum_link(int x,int y,int z);
void change_link(ct_node *p,int x);
int insert_link(ct_node *p,int x);
void remove_link(ct_node *p);
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);
    insert_link(p,z);
  }
  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)
        printf("Wrong link\n");
      else if(p->a==z-1)
        printf("Already controlled link\n");
      else if(a[x-1][z-1][1] || a[y-1][z-1][1])
        printf("Server overload\n");
      else{
        w=p->a;
        remove_link(p);
        if(insert_link(p,z-1)){
          insert_link(p,w);
          printf("Network redundancy\n");
        }
        else
          printf("Assignment done\n");
      }
    }
    else if(w==2){
      p=search(x-1,y-1);
      if(p)
        change_link(p,z);
      else
        change_link(search(y-1,x-1),z);
    }
    else{
      if(x==y){
        printf("No connection\n");
        continue;
      }
      w=sum_link(x-1,y-1,z-1);
      if(w==-1)
        printf("No connection\n");
      else
        printf("%d security devices placed\n",w);
    }
  }
  return 0;
}
int sum_link(int x,int y,int z){
  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;
}
void change_link(ct_node *p,int x){
  p->value=x;
  recalc(p);
  for(;p->parent;p=p->parent)
    recalc(p->parent);
  return;
}
int insert_link(ct_node *p,int x){
  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;
}
void remove_link(ct_node *p){
  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;
}