In this HackerEarth Strange Road System problem solution, Marichka will visit HackerLand, the country with N (1 <= N <= 10^5) cities, on her spring holidays. She feels very excited because of this.
During the next Q days one of the two following events happens.
– 1 U V P (1 <= U <= N, 1 <= V <= N, 1 <= P <= 10^9) — hackers build a new bidirectional road with happiness points $P$ between cities U and V
– 2 U V (1 <= U <= N, 1 <= V <= N) — Your task is to answer the query. You are given cities numbers — U and V, and your task is to find maximum happiness Marichka can get after travelling in some way(maybe through some intermediate cities) between cities U and V. If there is no way to get from the city U to the city V between them, then simply output -1.
If Marichka’s happiness before traversing some road was X and road’s happiness points are Y, then after traversing it Marichka’s happiness will be equal to X xor Y. Marichka can traverse one road many times. She also can visit some city many times during her travel.
Initially, there are no roads in HackerLand.
HackerEarth Strange Road System problem solution.
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
int n , m;
int p[100005]; //Parent array for DSU
int d[100005]; //Distance from the root in DSU
vector<int> b[100005]; //Linear basises for connected components
void add(int x , vector<int> &b) //Function to add x in linear basis
{
for(int i = 0; i < b.size(); i++)
{
int t= b[i];
if((x ^ t) < x)
{
x ^= t;
}
}
if(x == 0)
return;
for(int i = 0; i < b.size(); i++)
{
if((x ^ b[i]) < b[i])
b[i] ^= x;
}
b.pb(x); //Add x to linear basis
sort(b.begin() , b.end() , greater<int>());
}
int mx(int x , vector<int> &b)
{
for(int i = 0; i < b.size(); i++)
{
int t = b[i];
if((x ^ t) > x)
{
x ^= t;
}
}
return x;
}
int find(int u)
{
if(u == p[u])
return u;
int P = p[u];
int root = find(P);
d[u] ^= d[P];
p[u] = root;
return root;
}
void init(int n)
{
for(int i = 0; i < n; i++)
{
p[i] = i;
b[i].clear();
d[i] = 0;
}
}
void merge(int u , int v , int w) //Function to merge two vertices in DSU
{
int pu = find(u) , pv = find(v);
if(pu == pv) //If they are in the same set
{
add(w ^ d[u] ^ d[v] , b[pu]);
return;
}
p[pv] = pu;
d[pv] = d[v] ^ d[u] ^ w;
for(auto x : b[pv])
{
add(x , b[pu]); //Merging U-basis and V-basis
}
}
int main()
{
ios_base::sync_with_stdio(0);
int n;
assert(cin >> n);
assert(1 <= n && n <= 100000);
init(n);
int q;
cin >> q;
assert(1 <= q && q <= 100000);
while(q--)
{
int type;
assert(cin >> type);
assert(1 <= type && type <= 2);
if(type == 1)
{
int u , v , w;
assert(cin >> u >> v >> w);
assert(1 <= u && u <= n);
assert(1 <= v && v <= n);
assert(1 <= w && w <= 1e9);
u--;v--;
merge(u , v , w);
}
else
{
int u , v;
assert(cin >> u >> v);
assert(1 <= u && u <= n);
assert(1 <= v && v <= n);
u--;v--;
if(find(u) != find(v))
{
cout << -1 << endl;
continue;
}
//cout << d[u] << " " << d[v] << endl;
cout << mx(d[u] ^ d[v] , b[find(u)]) << endl;
}
}
}Second solution
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
int n , m;
int p[100005]; //Parent array for DSU
int d[100005]; //Distance from the root in DSU
vector<int> b[100005]; //Linear basises for connected components
void add(int x , vector<int> &b) //Function to add x in linear basis
{
for(int i = 0; i < b.size(); i++) // Iterating through all integers in basis to combine x with some elements of linear basis.
//As the result x should have minimum possible value
{
int t= b[i];
if((x ^ t) < x)
{
x ^= t;
}
}
if(x == 0) //If x is equal to zero, there is no need to add x to linear basis
return;
for(int i = 0; i < b.size(); i++) //If can make some elements of linear basis smaller, we should do this
{
if((x ^ b[i]) < b[i])
b[i] ^= x;
}
b.pb(x); //Add x to linear basis
sort(b.begin() , b.end() , greater<int>());
}
int mx(int x , vector<int> &b)
{
for(int i = 0; i < b.size(); i++)
{
int t = b[i];
if((x ^ t) > x)
{
x ^= t;
}
}
return x;
}
int find(int u)
{
if(u == p[u])
return u;
int P = p[u];
int root = find(P);
d[u] ^= d[P]; //Keeping d up-to-date
p[u] = root; //And p
return root;
}
void init(int n) // A standart function to initialize DSU
{
for(int i = 0; i < n; i++)
{
p[i] = i;
b[i].clear();
d[i] = 0;
}
}
void merge(int u , int v , int w)
{
int pu = find(u) , pv = find(v);
if(pu == pv) //If they are in the same set
{
add(w ^ d[u] ^ d[v] , b[pu]);
return;
}
p[pv] = pu;
d[pv] = d[v] ^ d[u] ^ w;
for(auto x : b[pv])
{
add(x , b[pu]); //Merging U-basis and V-basis
}
}
int main()
{
ios_base::sync_with_stdio(0);
int n;
assert(cin >> n);
assert(1 <= n && n <= 100000);
init(n);
int q;
cin >> q;
assert(1 <= q && q <= 100000);
while(q--)
{
int type;
assert(cin >> type);
assert(1 <= type && type <= 2);
if(type == 1)
{
int u , v , w;
assert(cin >> u >> v >> w);
assert(1 <= u && u <= n);
assert(1 <= v && v <= n);
assert(1 <= w && w <= 1e9);
u--;v--;
merge(u , v , w);
}
else
{
int u , v;
assert(cin >> u >> v);
assert(1 <= u && u <= n);
assert(1 <= v && v <= n);
u--;v--;
if(find(u) != find(v))
{
cout << -1 << endl;
continue;
}
cout << mx(d[u] ^ d[v] , b[find(u)]) << endl;
}
}
}