UVA – 10158 – War

  • Problem Statement : http://acm.uva.es/p/v101/10158.html
  • Type : Disjoint Sets, Union-Find Variant.
  • Solution :
    • It’s 4 days now and I’m sleeping and waking up on the same problem.  I really wasted so much time on trying to proof why it should work this way. but I really like idea behind it.
    • The solution starts by calculating the possibilities that when you are trying to set to pairs as friends for example.
      1. they could have been already friends.
      2. they could have been already enemies.
      3. they could be in a neutral set in-between.
    • the third case it what we are interested in. you have to make sure that all the people in this neutral set are so far neutral. it means that they have never been an enemy or a friend for someone outside their set.
#include <iostream>
#include <vector>
#include <stdio.h>
using namespace std;
#define F(ss) find(ss)
#define TWIN(ff) ((ff%2)?(ff+1):(ff-1))
#define T(ff) TWIN(ff)
#define ENEMIES(a, b) (F(b) == F(T(a)) || F(a) == F(T(b)))
#define FRIENDS(a, b) (F(a) == F(b) || F(T(a)) == F(T(b)))

vector<int> p;
void init(int N) {
	p = vector<int> (N + 1);
	for (int i = 1; i < N + 1; i++)
		p[i] = i;
}
int find(int a) {
	return p[a] == a ? a : (p[a] = find(p[a]));
}
void Union(int a, int b) {
	p[find(a)] = find(b);
}

int main() {
	int N;
	int C, f1, f2;

	while (scanf("%d", &N) == 1) {
		init(2 * N);
		while ((scanf("%d %d %d\n", &C, &f1, &f2) == 3)) {
			if (C == 0 && f1 == 0 && f2 == 0) break;
			f1 = 2*f1 +1, f2=2*f2+1;
			if (C == 1) {
				if (ENEMIES(f1, f2)) printf("-1\n");
				else  Union(f1, f2), Union(TWIN(f1), TWIN(f2));
			}
			if (C == 2) {
				if (FRIENDS(f1, f2)) printf("-1\n");
				else  Union(f1, TWIN(f2)), Union(f2, TWIN(f1));
			}
			if (C == 3) {
				if (FRIENDS(f1, f2)) printf("1\n");
				else printf("0\n");
			}
			if (C == 4) {
				if (ENEMIES(f1, f2)) printf("1\n");
				else printf("0\n");
			}
		}
	}

	return 0;
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: