[BOJ 20942] 신촌지역 초중고등학생 프로그래밍 대회 동아리 연합 대회

백준 20942번 신촌지역 초중고등학생 프로그래밍 대회 동아리 연합 대회

https://www.acmicpc.net/problem/20942

20942번: 신촌지역 초중고등학생 프로그래밍 대회 동아리 연합 대회

---

문제

N개의 자리가 있다.

각각의 자리에는 8세 ~ 19세의 참가자를 배치해야 한다.

 

M개의 연산에 대해, 두 자리에 대한 비트 연산(bitwise and, bitwise or)을 해서 특정 값을 만족해야 한다.

---

풀이

https://kdr06006.tistory.com/8

2-SAT

이 문제를 2-SAT으로 풀 수 있습니다.

 

각각의 자리마다 나이 제한이 있습니다. (8세 ~ 19세)

8 ~ 19는 5자리의 비트로 나타낼 수 있습니다.

 

N개의 자리를 N * 5개의 비트로 나타냅니다.

그리고 각 비트마다 0 또는 1 값을 가질 수 있으니 2개의 정점으로 추가로 분리해줍니다.

총 정점의 수 : N * 10 개

 

N을 N * 10으로 정점을 분리함

 

10 * N 개로 정점을 분리한 뒤, 각각에 고유 번호를 부여했습니다.

---

M개의 데이터에 대해 그래프 모델링을 해야합니다.

 

아래 4가지 경우의 수를 나눠서 정점을 연결해주면 됩니다.

 

x & y가 1인 경우

• x와 y 둘 다 1이 되어야 합니다.
• not(x) -> x, not(y) -> y 간선을 추가합니다.

x & y가 0인 경우

• x가 1이면, y는 0이 되어야 합니다.
• y가 1이면, x는 0이 되어야 합니다.
• x -> not(y), y -> not(x) 간선을 추가합니다.

x | y가 1인 경우

• x가 0이면, y는 1이 되어야 합니다.
• y가 0이면, x는 1이 되어야 합니다.
• not(x) -> y, not(y) -> x 간선을 추가합니다.

x | y가 0인 경우

• x와 y 둘 다 0이 되어야 합니다.
• x -> not(x), y -> not(y) 간선을 추가합니다.

---

N개의 자리에 대한 그래프 모델링도 해야합니다.

 

a가 0이 아닌 경우

해당 자리에 앉을 나이가 정해진 경우입니다.

각 비트에 대한 0 또는 1의 값이 명확히 할당되기 때문에 이에 맞게 간선을 만들어주면 됩니다.

 

비트의 값이 1이라면, not(x) -> x

비트의 값이 0이라면, x -> not(x)

 

a가 0인 경우

해당 자리에 앉을 나이가 정해지지 않은 경우입니다.

8 ~ 19의 값을 가지도록 간선을 만들어줘야 합니다.

---

N4가 0일 때

N4가 0이면, N3는 무조건 1이여야 합니다.

not(N4) -> N3 간선을 추가해 줍니다.

---

N4가 1일 때

N4가 1이면, N3와 N2가 0이여야 합니다.

N4 -> not(N3), N4 -> not(N2) 간선을 추가해 줍니다.

---

N3가 0일 때

N3가 0이면 N4는 1, N2는 0이여야 합니다.

not(N3) -> N4, not(N3) -> not(N2)를 추가해줍니다.

---

N3가 1일 때

N3가 1이면, N4는 0이여야 합니다.

N3 -> not(N4) 간선을 추가해 줍니다.

---

N2가 1일 때

N2가 1이면 N4는 0, N3는 1이여야 합니다.

N2 -> not(N4), N2 -> N3 간선을 추가해 줍니다.

---

총 필요한 간선은 N * 8 + M * 10 개 입니다.

 

N개의 자리 각각 8 ~ 19 사이의 수를 설정하기 위해 필요한 간선은 최대 8개 입니다.

M개의 연산에 대해 필요한 간선은 최대 10개 입니다.

 

바로 위의 그래프 모델링 과정을 확인하면 됩니다.

---

코드

#include <cstdio>

const int VSIZE = 5e4 * 5 * 2 + 4;
const int ESIZE = 5e4 * 8 + 1e5 * 10 + 4;

struct EdgePool {
	EdgePool* next;
	int x;
}edgePool[ESIZE];

int edgeCnt;

EdgePool* getEdge(int x) {
	edgePool[edgeCnt].x = x;
	return &edgePool[edgeCnt++];
}

struct Vector {
	EdgePool* head;

	void push(int x) {
		EdgePool* cur = getEdge(x);
		cur->next = head;
		head = cur;
	}
}adj[VSIZE];

struct Stack {
	int arr[VSIZE];
	int top = -1;

	inline bool empty() { return top == -1; }
	inline void push(int t) { arr[++top] = t; }
	inline int pop() { return arr[top--]; }
};

inline int get(int i, int j, int v) {
	return i * 10 + j * 2 + v;
}

inline int min(int a, int b) { return a < b ? a : b; }

struct SCC {
	Stack S;
	int dfsn[VSIZE], dfsNumber;
	int sccn[VSIZE], sccNumber;
	bool finish[VSIZE];

	int dfs(int cur) {
		int ret = dfsn[cur] = ++dfsNumber;
		S.push(cur);

		for (EdgePool* e = adj[cur].head; e; e = e->next) {
			int n = e->x;
			if (!dfsn[n]) ret = min(ret, dfs(n));
			else if (!finish[n]) ret = min(ret, dfsn[n]);
		}

		if (ret == dfsn[cur]) {
			++sccNumber;
			while (!S.empty()) {
				int t = S.pop();
				sccn[t] = sccNumber;
				finish[t] = true;
				if (t == cur) break;
			}
		}

		return ret;
	}

	void solve(int N) {
		register int i, j;
		for (i = 0; i < N; ++i) {
			for (j = 0; j < 5; ++j) {
				if (!dfsn[get(i, j, 0)]) dfs(get(i, j, 0));
				if (!dfsn[get(i, j, 1)]) dfs(get(i, j, 1));
			}
		}

		if (!TOF(N)) printf("0\n");
		else {
			printf("1\n");
			allocate(N);
		}
	}

	bool TOF(int N) {
		register int i, j;
		for (i = 0; i < N; ++i) {
			for (j = 0; j < 5; ++j) {
				if (sccn[get(i, j, 0)] == sccn[get(i, j, 1)])
					return false;
			}
		}

		return true;
	}

	void allocate(int N) {
		register int i, j;
		for (i = 0; i < N; ++i) {
			int ans = 0;

			for (j = 4; j >= 0; --j) {
				ans <<= 1;
				ans += sccn[get(i, j, 0)] > sccn[get(i, j, 1)];
			}

			printf("%d ", ans);
		}
	}
}scc;

inline void link(int n1, int n2) {
	adj[n1].push(n2);
}

int main()
{
	//freopen("input.txt", "r", stdin);

	register int i, j;
	int N;
	scanf("%d", &N);
	for (i = 0; i < N; ++i) {
		int t;
		scanf("%d", &t);
		if (t) {
			for (j = 0; j < 5; ++j) {
				if (t & 1) link(get(i, j, 0), get(i, j, 1));
				else link(get(i, j, 1), get(i, j, 0));
				t >>= 1;
			}
		}
		else {
			link(get(i, 4, 0), get(i, 3, 1));
			link(get(i, 4, 1), get(i, 3, 0));
			link(get(i, 4, 1), get(i, 2, 0));

			link(get(i, 3, 0), get(i, 4, 1));
			link(get(i, 3, 0), get(i, 2, 0));
			link(get(i, 3, 1), get(i, 4, 0));

			link(get(i, 2, 1), get(i, 4, 0));
			link(get(i, 2, 1), get(i, 3, 1));
		}
	}

	int M;
	char op;
	scanf("%d", &M);
	while (M--) {
		int x, y, z;
		scanf(" %c %d %d %d", &op, &x, &y, &z);
		--x; --y;

		for (j = 0; j < 5; ++j) {
			if (op == '&') {
				if (z & 1) {
					link(get(x, j, 0), get(x, j, 1));
					link(get(y, j, 0), get(y, j, 1));
				}
				else {
					link(get(x, j, 1), get(y, j, 0));
					link(get(y, j, 1), get(x, j, 0));
				}
			}
			else {
				if (z & 1) {
					link(get(x, j, 0), get(y, j, 1));
					link(get(y, j, 0), get(x, j, 1));
				}
				else {
					link(get(x, j, 1), get(x, j, 0));
					link(get(y, j, 1), get(y, j, 0));
				}
			}

			z >>= 1;
		}
	}

	scc.solve(N);
}