Network administration


Problem Statement :


Time Limits C:5, Cpp:5, C#:6, Java:8, Php:18, Ruby:20, Python:20, Perl:18, Haskell:10, Scala:14, Javascript:20, Pascal:5

Like every IT company, the Uplink Corporation has its own network. But, unlike the rest of the companies around the world, Uplink's network is subject to very specific restrictions:

Any pair of servers within the network should be directly connected by at most 1 link.
Each link is controlled by some specific network administrator.
No server has more than 2 links connected to it, that are controlled by the same administrator.
For easier management, links controlled by some administrator cannot be redundant (this is, removing any link will disconnect some two previously connected servers)
Notice that 2 connected servers might not have any direct link between them. Furthermore, in order to keep the network in a secured status, Uplink directives periodically try to perform some modifications over the network to mislead hackers. The problem is, having such a huge network, they need a software to efficiently simulate the network status after any of such modifications. You have been assigned to write the core section of that software.

Operations performed by the directives are:

Change the administrator assigned to some particular link.
Place some number of security devices along a particular link.
Also, given a network administrator, they would like to know how many devices are in the path created by links controlled by that administrator (if any) between 2 servers.


Input Format


Input begins with a line containing 4 integers  separated by a single whitespace, denoting the number of servers, links, network administrators and transformations, respectively.  lines follow each one with 3 integers  and , saying that there is a link between server  and server , and that link is controlled by administrator . Initially, network topology fulfills the restrictions described above and there is no security device along any link. Remaining  lines in the input follow one the next formats:

   
meaning that link between server  and server   is requested to be assigned to administrator 

   
meaning that the number of security devices along the link between server  and server   will be fixed to , removing any existing devices on this link before the operation. The involved link will always exist.

   
meaning that directives want to know the number of security devices placed along the path between server  and server , just considering links controlled by administrator .

Output Format

For each network transformation in the form     you should output:

"Wrong link" if there is no direct link between server  and server .
"Already controlled link" if the requested link does exist, but it is already controlled by administrator .
"Server overload" if administrator  already controls 2 links connected to one of the involved servers.
"Network redundancy" if the requested assignment creates no new connection considering just the links controlled by .
"Assignment done" if none of the above conditions holds. In this case, link directly connecting  with  is assigned to .
For each network transformation in the form     you should output:

"No connection" if there is no path between the requested servers considering just the links controlled by .
" 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 .


Constraints


1  <=   S  <=   10^5
1  <=   L   <=  5 * 10^5
1  <=   A  <=  10^2
1  <=   T  <=   5 * 10^5
1  <=  x  <=  2000


Solution :



title-img 


                            Solution in C :

In   C++  :







#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;
}









In   Java :






import java.io.*;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Random;

public class HR_net_admin {

static class Node {
Node l = null, r = null, p = null;
boolean reversed = false;
int value = 0, sum = 0;
int u, v, admin;

Node(int u, int v, int admin) {
this.u = u;
this.v = v;
this.admin = admin;
}
}

static int sum(Node n) {
return n == null ? 0 : n.sum;
}

static void fixUp(Node n) {
n.sum = n.value + sum(n.l) + sum(n.r);
}

static void fixDown(Node n) {
if (n.reversed) {
Node tmp = n.l;
n.l = n.r;
n.r = tmp;
int ti = n.u;
n.u = n.v;
n.v = ti;
if (n.l != null) {
n.l.reversed ^= true;
}
if (n.r != null) {
n.r.reversed ^= true;
}
n.reversed = false;
}
}

static void rotate(Node x) {
Node y = x.p;
x.p = y.p;
if (y.p != null) {
if (y == y.p.l) {
y.p.l = x;
} else {
y.p.r = x;
}
}
y.p = x;
if (x == y.l) {
y.l = x.r;
if (y.l != null) {
y.l.p = y;
}
x.r = y;
} else {
y.r = x.l;
if (y.r != null) {
y.r.p = y;
}
x.l = y;
}
fixUp(y);
fixUp(x);
}

static Node splay(Node x) {
while (x.p != null) {
if (x.p.p != null) {
fixDown(x.p.p);
}
fixDown(x.p);
fixDown(x);
if (x.p.p == null) {
rotate(x);
} else {
if (x == x.p.l && x.p == x.p.p.l || x == x.p.r && x.p == x.p.p.r) {
rotate(x.p);
rotate(x);
} else {
rotate(x);
rotate(x);
}
}
}
return x;
}

static Node join(Node l, Node x, Node r) {
x.reversed = false;
x.l = l;
x.r = r;
if (l != null) {
l.p = x;
}
if (r != null) {
r.p = x;
}
fixUp(x);
return x;
}

static Node q, r;

static void split(Node x) {
splay(x);
fixDown(x);
if (x.l != null) {
x.l.p = null;
}
if (x.r != null) {
x.r.p = null;
}
x.p = null;
q = x.l;
r = x.r;
x.l = x.r = null;
fixUp(x);
}

static Node min(Node n) {
fixDown(n);
while (n.l != null) {
n = n.l;
fixDown(n);
}
splay(n);
return n;
}

static Node max(Node n) {
fixDown(n);
while (n.r != null) {
n = n.r;
fixDown(n);
}
splay(n);
return n;
}

public static void solve(Input in, PrintWriter out)
 throws IOException {
int n = in.nextInt(); // servers
int m = in.nextInt(); // links
int k = in.nextInt(); // admins
int q = in.nextInt(); // queries
HashMap<Integer, Node>[] edges = new HashMap[n];
HashMap<Integer, Node[]>[] admins = new HashMap[n];
for (int i = 0; i < n; ++i) {
edges[i] = new HashMap<>();
admins[i] = new HashMap<>();
}
for (int i = 0; i < m; ++i) {
int u = in.nextInt() - 1;
int v = in.nextInt() - 1;
int a = in.nextInt() - 1;
Node e = new Node(u, v, a);
edges[u].put(v, e);
edges[v].put(u, e);
insert(e, admins);
}
for (int i = 0; i < q; ++i) {
int t = in.nextInt();
if (t == 1) {
int u = in.nextInt() - 1;
int v = in.nextInt() - 1;
int a = in.nextInt() - 1;
if (!edges[u].containsKey(v)) {
out.println("Wrong link");
continue;
}
Node e = edges[u].get(v);
if (e.admin == a) {
out.println("Already controlled link");
continue;
}
Node l = null, r = null;
if (admins[u].containsKey(a)) {
Node[] ar = admins[u].get(a);
if (ar.length > 1) {
out.println("Server overload");
continue;
}
if (ar.length == 1) {
l = ar[0];
}
}
if (admins[v].containsKey(a)) {
Node[] ar = admins[v].get(a);
if (ar.length > 1) {
out.println("Server overload");
continue;
}
if (ar.length == 1) {
r = ar[0];
}
}
if (l != null && r != null && min(splay(l)) == min(splay(r))) {
out.println("Network redundancy");
continue;
}
admins[u].put(e.admin, remove(admins[u].get(e.admin), e));
admins[v].put(e.admin, remove(admins[v].get(e.admin), e));
split(e);
e.admin = a;
insert(e, admins);
out.println("Assignment done");
} else if (t == 2) {
int u = in.nextInt() - 1;
int v = in.nextInt() - 1;
int x = in.nextInt();
if (!edges[u].containsKey(v)) {
throw new AssertionError();
}
Node e = edges[u].get(v);
splay(e);
e.value = x;
fixUp(e);
} else if (t == 3) {
int u = in.nextInt() - 1;
int v = in.nextInt() - 1;
int a = in.nextInt() - 1;
Node l = any(u, a, admins);
Node r = any(v, a, admins);
if (l == null || r == null || min(splay(l)) != min(splay(r))) {
out.println("No connection");
continue;
}
int prefixU = prefix(u, a, l);
int prefixV = prefix(v, a, r);
out.println(Math.abs(prefixU - prefixV) + " security devices placed");
}
}
}

private static int prefix(int u, int a, Node e) {
splay(e);
fixDown(e);
if (u == e.u) {
return sum(e.l);
} else if (u == e.v) {
return sum(e.l) + e.value;
} else {
throw new AssertionError();
}
}

private static Node any(int u,
 int a, HashMap<Integer, Node[]>[] admins) {
Node[] ar = admins[u].get(a);
return ar == null || ar.length == 0 ? null : ar[0];
}

private static Node insert(Node e, 
HashMap<Integer, Node[]>[] admins) {
int u = e.u;
int v = e.v;
fixDown(e);
int a = e.admin;
Node l = null, r = null;
if (admins[u].containsKey(a)) {
Node[] ar = admins[u].get(a);
if (ar.length > 1) {
throw new AssertionError();
}
if (ar.length == 1) {
l = ar[0];
}
}
if (admins[v].containsKey(a)) {
Node[] ar = admins[v].get(a);
if (ar.length > 1) {
throw new AssertionError();
}
if (ar.length == 1) {
r = ar[0];
}
}
if (l != null && r != null && min(splay(l)) == min(splay(r))) {
throw new AssertionError();
}
if (l != null && max(splay(l)).v != u) {
splay(l).reversed ^= true;
if (max(splay(l)).v != u) {
throw new AssertionError();
}
}
if (r != null && min(splay(r)).u != v) {
splay(r).reversed ^= true;
if (min(splay(r)).u != v) {
throw new AssertionError();
}
}
admins[u].put(a, append(admins[u].get(a), e));
admins[v].put(a, append(admins[v].get(a), e));
return join(l, e, r);
}

private static Node[] append(Node[] ar, Node e) {
if (ar == null) {
return new Node[] {e};
}
ar = Arrays.copyOf(ar, ar.length + 1);
ar[ar.length - 1] = e;
return ar;
}

private static Node[] remove(Node[] ar, Node e) {
if (ar == null) {
throw new AssertionError();
}
Node[] ar1 = new Node[ar.length - 1];
int len = 0;
for (int i = 0; i < ar.length; ++i) {
if (ar[i] != e) {
ar1[len++] = ar[i];
}
}
if (len != ar1.length) {
throw new AssertionError();
}
return ar1;
}

public static void main(String[] args)
throws IOException {
PrintWriter out = new PrintWriter(System.out);

solve(new Input(new BufferedReader(
    new InputStreamReader(System.in))), out);
out.close();
}

private static boolean cdfs(int i, int p, int[][] g, boolean[] col, int c) {
int count = 0;
col[i] = true;
for (int j = 0; j < g.length; ++j) {
if (g[i][j] != c || j == p) {
continue;
}
if (col[j] || !cdfs(j, i, g, col, c)) {
return false;
}
count++;
}
return count <= (p == -1 ? 2 : 1);
}

public static void solveSlow(Input in,
 PrintWriter out) throws IOException {
int n = in.nextInt(); // servers
int m = in.nextInt(); // links
int k = in.nextInt(); // admins
int q = in.nextInt(); // queries
int[][] g = new int[n][n];
for (int[] ar : g) {
Arrays.fill(ar, -1);
}
int[][] c = new int[n][n];
for (int i = 0; i < m; ++i) {
int u = in.nextInt() - 1;
int v = in.nextInt() - 1;
int a = in.nextInt() - 1;
g[u][v] = g[v][u] = a;
}
for (int it = 0; it < q; ++it) {
int t = in.nextInt();
if (t == 1) {
int u = in.nextInt() - 1;
int v = in.nextInt() - 1;
int a = in.nextInt() - 1;
if (g[u][v] == -1) {
out.println("Wrong link");
continue;
}
if (g[u][v] == a) {
out.println("Already controlled link");
continue;
}
int uc = 0, vc = 0;
for (int i = 0; i < n; ++i) {
if (g[u][i] == a) {
uc++;
}
if (g[v][i] == a) {
vc++;
}
}
if (uc == 2 || vc == 2) {
out.println("Server overload");
continue;
}
int[] d = new int[n];
Arrays.fill(d, -1);
dfs(u, 0, a, g, c, d);
if (d[v] != -1) {
out.println("Network redundancy");
continue;
}
g[u][v] = g[v][u] = a;
out.println("Assignment done");
} else if (t == 2) {
int u = in.nextInt() - 1;
int v = in.nextInt() - 1;
int x = in.nextInt();
c[u][v] = c[v][u] = x;
} else if (t == 3) {
int u = in.nextInt() - 1;
int v = in.nextInt() - 1;
int a = in.nextInt() - 1;
int[] d = new int[n];
Arrays.fill(d, -1);
dfs(u, 0, a, g, c, d);
if (d[v] == -1) {
out.println("No connection");
continue;
}
out.println(d[v] + " security devices placed");
}
}
}

private static void dfs(int i, int dist, int a, 
int[][] g, int[][] c, int[] d) {
if (d[i] != -1) {
return;
}
d[i] = dist;
for (int j = 0; j < g.length; ++j) {
if (g[i][j] == a) {
dfs(j, dist + c[i][j], a, g, c, d);
}
}
}

static class Input {
BufferedReader in;
StringBuilder sb = new StringBuilder();

public Input(BufferedReader in) {
this.in = in;
}

public Input(String s) {
this.in = new BufferedReader(new StringReader(s));
}

public String next() throws IOException {
sb.setLength(0);
while (true) {
int c = in.read();
if (c == -1) {
return null;
}
if (" \n\r\t".indexOf(c) == -1) {
sb.append((char)c);
break;
}
}
while (true) {
int c = in.read();
if (c == -1 || " \n\r\t".indexOf(c) != -1) {
break;
}
sb.append((char)c);
}
return sb.toString();
}

public int nextInt() throws IOException {
return Integer.parseInt(next());
}

public long nextLong() throws IOException {
return Long.parseLong(next());
}

public double nextDouble() throws IOException {
return Double.parseDouble(next());
}
}
}










In    C  :







#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;
}








View More Similar Problems

Array Pairs

Consider an array of n integers, A = [ a1, a2, . . . . an] . Find and print the total number of (i , j) pairs such that ai * aj <= max(ai, ai+1, . . . aj) where i < j. Input Format The first line contains an integer, n , denoting the number of elements in the array. The second line consists of n space-separated integers describing the respective values of a1, a2 , . . . an .

View Solution →

Self Balancing Tree

An AVL tree (Georgy Adelson-Velsky and Landis' tree, named after the inventors) is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property. We define balance factor for each node as : balanceFactor = height(left subtree) - height(righ

View Solution →

Array and simple queries

Given two numbers N and M. N indicates the number of elements in the array A[](1-indexed) and M indicates number of queries. You need to perform two types of queries on the array A[] . You are given queries. Queries can be of two types, type 1 and type 2. Type 1 queries are represented as 1 i j : Modify the given array by removing elements from i to j and adding them to the front. Ty

View Solution →

Median Updates

The median M of numbers is defined as the middle number after sorting them in order if M is odd. Or it is the average of the middle two numbers if M is even. You start with an empty number list. Then, you can add numbers to the list, or remove existing numbers from it. After each add or remove operation, output the median. Input: The first line is an integer, N , that indicates the number o

View Solution →

Maximum Element

You have an empty sequence, and you will be given N queries. Each query is one of these three types: 1 x -Push the element x into the stack. 2 -Delete the element present at the top of the stack. 3 -Print the maximum element in the stack. Input Format The first line of input contains an integer, N . The next N lines each contain an above mentioned query. (It is guaranteed that each

View Solution →

Balanced Brackets

A bracket is considered to be any one of the following characters: (, ), {, }, [, or ]. Two brackets are considered to be a matched pair if the an opening bracket (i.e., (, [, or {) occurs to the left of a closing bracket (i.e., ), ], or }) of the exact same type. There are three types of matched pairs of brackets: [], {}, and (). A matching pair of brackets is not balanced if the set of bra

View Solution →