Russia And Ukraine -Editorial|| RUSUKR

editorial
,
1

PROBLEM LINK: Russia And Ukraine | CodeChef

Problem Code: Russia And Ukraine | CodeChef

Practice: CodeChef: Practical coding for everyone

Contest : Internal Contest CodeChef Adgitm Coding Competition | CodeChef

Author: Codechef Adgitm Chapter : https://www.codechef.com/users/test_account_9
Tester: Codechef Adgitm Chapter : https://www.codechef.com/users/test_account_9
Editorialist: Codechef Adgitm Chapter : https://www.codechef.com/users/test_account_9

DIFFICULTY:

Hard

PROBLEM:

A Mahayudh is being led between two countries, Ukraine and Russia. As a loyal citizen of India, you decide to help your country’s espionage by attending the peace talks taking place these days (incognito, of course). There are “p” people at the talks (not including you), but you do not know which person belongs to which country. You can see people talking to each other, and through observing their nature during their occasional one-to-one conversations, you can guess if they are Friends or Bad. In fact what your country would need to know is whether certain pairs of people are from the same country, or they are Bad. You may receive such questions from the Indian government even during the peace talks, and you have to give replies on the basis of your observations so far. Fortunately, nobody talks to you, as nobody pays attention to your humble appearance.
Now, more formally, consider a black box with the following operations:

  • setFriends(x,y) shows that x and y are from the same country
  • setBad(x,y) shows that x and y are from different countries
  • areFriends(x,y) returns true if you are sure that x and y are friends
  • areBad(x,y) returns true if you are sure that x and y are Bad

The first two operations should signal an error if they contradict your former knowledge. The two relations ‘friends’ (denoted by ∼) and ‘Bad’ (denoted by ∗) have the following properties:
∼ is an equivalence relation, i.e.

  1. If x ∼ y and y ∼ z then x ∼ z (The friends of my friends are my friends as well.
  2. If x ∼ y then y ∼ x (Friendship is mutual.)
  3. x ∼ x (Everyone is a friend of himself.)

∗ is symmetric and irreflexive

  1. If x ∗ y then y ∗ x (Hatred is mutual.)
  2. Not x ∗ x (Nobody is an enemy of himself.)

Also

  1. If x ∗ y and y ∗ z then x ∼ z (A common enemy makes two people friends.
  2. If x ∼ y and y ∗ z then x ∗ z (An enemy of a friend is an enemy. Operations setFriends(x,y) and setBad(x,y) must preserve these properties.

EXPLANATION:

Since the relation of friends is transitive, we can keep sets in which all the people in a set are friends. For each of these sets of friends, there will also be a set of Bad made up of the union of all the Bad of each person in the set of friends. Every person in this set of Bad will be an Bad of every person in the set of friends. To see why this is true, consider a person aaa in the set of friends F. Their Bad is bbb in the set of Bad E. Since an Bad of a friend is also an Bad, bb will be the Bad of all of aaa’s friends, which are the other people F. Furthermore, each person in E is friends with all other people in E, since they share a common Bad aaa.

To represent this, sets 0…n−10 \dots n - 10…n−1 in the code will be sets of friends, while each set iii in sets n…2n−1n \dots 2n - 1n…2n−1 will be be the Bad of set i−ni - ni−n.

For each query we let the people x and y and a root of x’s friend , y’s friends and x’s Bad, y’s Bad

areBad

If any of xxx’s friends are friends with any of yyy’s Bad, then xxx will be friends with one of y’s Bad. Thus, x and y will be Bad. To check if this is the case, we check if xroot is the same as eyroot(which means that x’s friends are y’s Bad), or if yroot is the same as exroot (which means that y’s friends are x’s Bad).

areFriends

If x and y are in the same set, then they are friends.

setBad

When setting two people as Bad, we need to check if they are friends. We can use the areFriends function to do this. If they are not friends, we join xroot’s set with eyroot’s set and join yroot’s set with exroot’s set, since the friend of an Bad is also an Bad.

setFriends

If we want to set two people as friends, we first need to check if they are Bad, using the areBad function. If they are not Bad, we can join xroot’s and yroot’s sets. The Bad of two sets of friends will also become friends, so we also join exroot’s and eyroot’s sets.

SOLUTION:

C++:

#include<bits/stdc++.h>
using namespace std;
int n;
int father[N];
int opt, x, y;

void inp(){
cin >> n;
rep(i,0,2*n-1)
father[i] = i;
}

int finding(int u){
if(u!=father[u])
father[u] = finding(father[u]);
return father[u];
}

void join(int u, int v){
int uu = finding(u);
int vv = finding(v);
if(uu==vv) return;
father[uu] = vv;
}

void process(){
while(cin >> opt >> x >> y){
if(opt==0 && x==0 && y==0) break;
if(opt==1){
if(finding(x)==finding(y+n)){
cout << -1 << ‘\n’;
continue;
}
join(x, y), join(x + n, y + n);
}
else if(opt==2){
if(finding(x)==finding(y)){
cout << -1 << ‘\n’;
continue;
}
join(x, y+n), join(x+n, y);
}
else if(opt==3){
if(finding(x)==finding(y))
cout << 1 << ‘\n’;
else cout << 0 << ‘\n’;
}
else{
if(finding(x)==finding(y+n))
cout << 1 << ‘\n’;
else cout << 0 << ‘\n’;
}
}
}

int main() {
inp();
process();
return 0;
}