CORNET - Corporative Network - SOLUTION

I' am assuming that you've already understood the problem otherwise go back and read the problem once again : PROBLEM STATEMENT.

If you are not familiar with DSU, I suggest you to go and read this article first: DSU

It is a simple DSU problem in which whenever a query starts with 'I' you have to do union of A and B, where A is always a server, but B may be or may not be a server. And at every union you have to set distance from A to B = |A-B|%1000.

Now let us talk about the queries starting with 'E'. At every query starting with 'E' you have to tell the distance of that enterprise from its server. It is also possible that the given building is server itself, then the difference will be equal to '0'. We have kept an array 'd' which is storing distance of ith enterprise from its server.
Assume that the query is 'E A' and the enterprise serving to A is D in the following manner:
A -> B -> C -> D
While finding the distance from A to D we will update all distances of enterprises from A to D, i.e., we will update d[A], d[B] and d[C].

While telling the distance from server to that  enterprise you don't need to do any %1000 thing!

Now, I hope you can implement the code yourself or refer to the following code:

	#include "bits/stdc++.h"
	using namespace std;
	typedef unsigned long long ull;
	typedef long long int ll;
	typedef vector<long long int> vi;
	typedef pair<int, int> ii;
	typedef vector<ii> vii;
	int visit[23456];
	int d[23456];
	void update(int count, int x, int y)
	{
	while(x!=visit[x])
	{
	ll t=count-d[x];
	d[x]=count;
	count=t;
	ll z=visit[x];
	visit[x]=y;
	x=z;
	}
	}
	int len(int x)
	{
	int y=x;
	ll count=0;
	while(x!=visit[x])
	{
	count=(count+(d[x]));
	x=visit[x];
	}
	update(count,y,x);
	}
	void unin(int a,int b)
	{
	visit[a]=b;
	d[a] = abs(a-b)%1000;
	}
	int main()
	{
	ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
	ll t;
	cin>>t;
	while(t--)
	{
	memset(d,0,sizeof(d));
	memset(visit,0,sizeof(visit));
	ll n;
	cin>>n;
	while(1)
	{
	char a;
	int x,y;
	cin>>a;
	if(a=='O')
	break;
	else if(a=='E')
	{
	cin>>x;
	if(!visit[x])
	visit[x]=x;
	len(x);
	cout<<d[x]<<endl;
	}
	else
	{
	cin>>x>>y;
	if(!visit[y])
	visit[y]=y;
	if(!visit[x])
	visit[x]=x;
	unin(x,y);
	}
	}
	}
	return 0;
	}

view raw CORNET.cpp hosted with ❤ by GitHub