# BF21JA - Editorial

[Practice ]( Help Jimmy! | CodeChef)

MEDIUM

# PREREQUISITES

Disjoint Sets, Simple Math

# PROBLEM

You are given a Jam Board with R rows and C columns. A row of the jambaord contains a group of 5 points arranged vertically, which are connected with the same metal plate. So you have a grid of 5*R rows and C columns.

You are to simulate the following 4 operations

• Add a wire connecting two grid points.
• Give potential to a grid point.
• Remove potential from a grid point.
• Check if there is potential difference between two grid points. (Since potential difference leads to LED being on)

# QUICK EXPLANATION

This would be an entirely different problem if we were to allow for removal of a wire that connects two grid points. Since that is not allowed, the problem reduces to maintaining disjoint sets of groups. Also known as Union Find. We have to make a tiny modification though - to maintain the number of sources providing potential to each group.

The number of sources are easy to maintain.

• Augment the Join method in your Disjoing Sets data structure to add and store the potential on the root for the whole group.
• Addition and Removal of a source of potential for a group are simply performed at the root of the group.

# SOLUTION (in C++) :

#include <bits/stdc++.h>

using namespace std;

#define ll long long int
const int mod = 1e9 + 7;

int n, row, cols;

int getValue(int x, int y) {
return ((y - 1) / 5) * cols + x - 1;
}

int parent[1250010];
int mrank[1250010];
int voltage[1250010];

int decrypt(char s[]) {
int a = 0, b = 0;
if (s[0] & 32)a += s[0] - 'a' + 26;
else a += s[0] - 'A';
a = a * 52;
if (s[1] & 32)a += s[1] - 'a' + 26;
else a += s[1] - 'A';
if (s[2] & 32)b += s[2] - 'a' + 26;
else b += s[2] - 'A';
b = b * 52;
if (s[3] & 32)b += s[3] - 'a' + 26;
else b += s[3] - 'A';
return getValue(a, b);
}

int findParent(int x) {
if (parent[x] == x)return x;
else return parent[x] = findParent(parent[x]);
}

voltage[x]++;
}

void removeSource(int x) {
voltage[x]--;
assert(voltage[x] >= 0);
}

bool getVoltage(int x) {
return voltage[x] != 0;
}

void merge(int x, int y) {
int px = findParent(x);
int py = findParent(y);
if (px != py) {
if (mrank[px] >= mrank[py]) {
parent[py] = px;
mrank[px]++;
voltage[px] += voltage[py];
} else {
parent[px] = py;
mrank[py]++;
voltage[py] += voltage[px];
}
}
}

int main() {
//code
char st[16];
scanf("%d%d%d", &n, &row, &cols);
for (int i = 0; i <= (row * cols); i++) {
parent[i] = i;
mrank[i] = 0;
voltage[i] = 0;
}
while (n--) {
scanf("%s", st);
switch (st[0]) {
case 'W': {
int s1 = decrypt(st + 1);
int s2 = decrypt(st + 5);
//cout<<s1<<" "<<s2<<endl;
merge(s1, s2);
}
break;
case 'V': {
int s1 = decrypt(st + 1);
//cout<<s1<<endl;
}
break;
case 'R': {
int s1 = decrypt(st + 1);
//cout<<s1<<endl;
removeSource(findParent(s1));
}
break;
case 'L': {

int s1 = decrypt(st + 1);
int s2 = decrypt(st + 5);
//cout<<s1<<" "<<s2<<endl;
if (getVoltage(findParent(s1)) != getVoltage(findParent(s2))) {
printf("ON \n");
} else {
printf("OFF \n");
}
}
break;
}
}

return 0;
}