[BOJ 16853] 필름

문제

---

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

풀이

---

각 필름마다 RGB에 해당하는 3개의 변수를 만들어 주고, 각 단색광을 포함하면 True, 아니면 False라고 놓는다.

K가 H이고 단색광이 C1, C2에 모두 포함되면 두 필름 모두에 그 단색광이 포함되어야 한다.

K가 H이고 단색광이 C1에만 포함되면 적어도 한 필름은 그 단색광을 포함하지 않는다.

K가 L이고 단색광이 C1, C2에 모두 포함되면 적어도 한 필름은 그 단색광을 포함한다.

K가 L이고 단색광이 C1에만 포함되면 두 필름 모두 그 단색광을 포함하지 않는다.

위 네 경우에 대해 간선을 추가해 주면 된다.

참고로 C1에 포함되지 않은 단색광이 C2에 포함되면 그 즉시 유효하지 않은 실험 기록이 된다.

MLE 때문에 pypy가 아닌 python으로 제출했다.

코드

---

import sys
sys.setrecursionlimit(3 * 10 ** 5)

n, m = map(int, sys.stdin.readline().split())
graph = [[] for _ in range(6 * n + 1)]
color = {'BLACK': 0, 'RED': 1, 'GREEN': 2, 'YELLOW': 3, 'BLUE': 4, 'PURPLE': 5, 'CYAN': 6, 'WHITE': 7}

for _ in range(m):
    a, b, k, c, d = sys.stdin.readline().split()
    a = 3 * int(a) - 3
    b = 3 * int(b) - 3
    c = color[c]
    d = color[d]
    if k == 'H':
        for i in range(3):
            if c & (1 << i):
                if d & (1 << i):
                    graph[-a - i - 1].append(a + i + 1)
                    graph[-b - i - 1].append(b + i + 1)
                else:
                    graph[a + i + 1].append(-b - i - 1)
                    graph[b + i + 1].append(-a - i - 1)
            elif d & (1 << i):
                print('THINKINGFACE')
                exit()
    else:
        for i in range(3):
            if c & (1 << i):
                if d & (1 << i):
                    graph[-a - i - 1].append(b + i + 1)
                    graph[-b - i - 1].append(a + i + 1)
                else:
                    graph[a + i + 1].append(-a - i - 1)
                    graph[b + i + 1].append(-b - i - 1)
            elif d & (1 << i):
                print('THINKINGFACE')
                exit()

stack = []
scc_num = 1
scc_idx = [0] * (6 * n + 1)
finish = [0] * (6 * n + 1)
visit = [0] * (6 * n + 1)
idx = 1


def dfs(cur):
    global idx, scc_num
    visit[cur] = idx
    low = idx
    idx += 1
    stack.append(cur)

    for nxt in graph[cur]:
        if not visit[nxt]:
            low = min(low, dfs(nxt))
        elif not finish[nxt]:
            low = min(low, visit[nxt])

    if low == visit[cur]:
        while stack:
            top = stack.pop()
            finish[top] = 1
            scc_idx[top] = scc_num
            if cur == top:
                break

        scc_num += 1

    return low


for i in range(1, 6 * n + 1):
    if not visit[i]:
        dfs(i)

for i in range(1, 3 * n + 1):
    if scc_idx[i] == scc_idx[-i]:
        print('THINKINGFACE')
        break
else:
    print('ALIEN')