Skip to content
Programming101
Programmingoneonone

Learn everything about programming

  • Home
  • CS Subjects
    • IoT – Internet of Things
    • Digital Communication
    • Human Values
  • Programming Tutorials
    • C Programming
    • Data structures and Algorithms
    • 100+ Java Programs
    • 100+ C Programs
  • HackerRank Solutions
    • HackerRank Algorithms Solutions
    • HackerRank C problems solutions
    • HackerRank C++ problems solutions
    • HackerRank Java problems solutions
    • HackerRank Python problems solutions
Programming101
Programmingoneonone

Learn everything about programming

HackerEarth Strange Road System problem solution

YASH PAL, 31 July 2024
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

Topics we are covering

Toggle
  • HackerEarth Strange Road System problem solution.
    • Second solution

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

}
coding problems solutions

Post navigation

Previous post
Next post
  • Automating Image Format Conversion with Python: A Complete Guide
  • HackerRank Separate the Numbers solution
  • How AI Is Revolutionizing Personalized Learning in Schools
  • GTA 5 is the Game of the Year for 2024 and 2025
  • Hackerrank Day 5 loops 30 days of code solution
How to download udemy paid courses for free

Pages

  • About US
  • Contact US
  • Privacy Policy

Programing Practice

  • C Programs
  • java Programs

HackerRank Solutions

  • C
  • C++
  • Java
  • Python
  • Algorithm

Other

  • Leetcode Solutions
  • Interview Preparation

Programming Tutorials

  • DSA
  • C

CS Subjects

  • Digital Communication
  • Human Values
  • Internet Of Things
  • YouTube
  • LinkedIn
  • Facebook
  • Pinterest
  • Instagram
©2025 Programmingoneonone | WordPress Theme by SuperbThemes