468B


  Posted on 02 Dec 2014
disjoint sets

Description


We have () distinct integers , and . There are two sets and . If belongs to , must also contains . It is the same with and . Output how s can be divided into the two sets. Each belongs and only belongs to one set.

Tutorial


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

In additon, we should also know that if does not exist, can only belong to . It is the same as .

So we can use Disjoint Sets to solve this problem. Join the s that must belongs to one set. Join those who must belong to with a special node. Join those who must belong to 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 and .

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