## 468B

Posted on 02 Dec 2014
disjoint sets

### Description

We have $n$ ($1 \leq n \leq 10^5$) distinct integers $q_1~q_n$, $a$ and $b$. There are two sets $A$ and $B$. If $x$ belongs to $A$, $A$ must also contains $a-x$. It is the same with $B$ and $b$. Output how $q$s can be divided into the two sets. Each $q$ belongs and only belongs to one set.

### Tutorial

If we have number $x$ and $a-x$, they should be in the same set. If $x$ belongs to $A$, it is obvious that $a-x$ belongs to $A$. If $x$ is not in $A$, then $a-x$ cannot find its partner in $A$, so they it cannot be in $A$ any more. Therefore, they can only all be in $B$. It is the same as the number x, b - x.

In additon, we should also know that if $a-x$ does not exist, $x$ can only belong to $B$. It is the same as $A$.

So we can use Disjoint Sets to solve this problem. Join the $q$s that must belongs to one set. Join those who must belong to $A$ with a special node. Join those who must belong to $B$ with another special node. Finally, if the two special nodes are in joined, there is no solution. Otherwise, solution exists.

Use STL map to get the positions of $a-x$ and $b-x$.

### Solution

#include <cstdio>
#include <map>
#include <algorithm>
using namespace std;

#define D(x)
#define MAX_N 100005

int sum_a, sum_b;
int f[MAX_N];
int n;

struct Disjoint_sets
{
int father[MAX_N];

Disjoint_sets()
{}

Disjoint_sets(int n)
{
for (int i = 0; i < n; i++)
{
father[i] = i;
}
}

int root(int a)
{
int ret = a;
while (father[ret] != ret)
ret = father[ret];
while (father[a] != a)
{
int b = a;
a = father[a];
father[b] = ret;
}
return ret;
}

void join(int a, int b)
{
father[root(a)] = father[root(b)];
}
}d_set;

void input()
{
scanf("%d%d%d", &n, &sum_a, &sum_b);
for (int i = 0; i < n; i++)
{
scanf("%d", &f[i]);
}
}

bool work()
{
d_set = Disjoint_sets(n + 2);
map<int, int> pos;
for (int i = 0; i < n; i++)
{
pos[f[i]] = i;
}
for (int i = 0; i < n; i++)
{
if (pos.find(sum_a - f[i]) != pos.end())
{
d_set.join(i, pos[sum_a - f[i]]);
}else
{
d_set.join(i, n);
}
if (pos.find(sum_b - f[i]) != pos.end())
{
d_set.join(i, pos[sum_b - f[i]]);
}else
{
d_set.join(i, n + 1);
}
}
return d_set.root(n) != d_set.root(n + 1);
}

void output()
{
puts("YES");
for (int i = 0; i < n; i++)
{
if (i != 0)
{
putchar(' ');
}
if (d_set.root(i) == d_set.root(n))
{
putchar('1');
}else
{
putchar('0');
}
}
}

int main()
{
input();
if (!work())
{
puts("NO");
}else
{
output();
}
return 0;
}