BOJ - 16388 - Is-A? Has-A? Who Knowz-A?

Updated:

import sys

def solution():
    data_ = {}
    
    N, M = map(int, sys.stdin.readline().split())
    is_a = [[0 for _ in range(500)] for _ in range(500)]
    has_a = [[0 for _ in range(500)] for _ in range(500)]

    index = 0
    for _ in range(N):
        C1, R, C2 = map(str, sys.stdin.readline().split())

        if C1 in data_: pass
        else:
            data_[C1] = index
            index += 1

        if C2 in data_: pass
        else:
            data_[C2] = index
            index += 1

        if R == "is-a":
            is_a[data_[C1]][data_[C2]] = 1
        elif R == "has-a":
            has_a[data_[C1]][data_[C2]] = 1

    for k in range(len(data_)):
        for i in range(len(data_)):
            for j in range(len(data_)):
                is_a[i][j] = is_a[i][j] | (is_a[i][k] & is_a[k][j])
                has_a[i][j] = has_a[i][j] | (has_a[i][k] & has_a[k][j])
                has_a[i][j] = has_a[i][j] | (is_a[i][k] & has_a[k][j])
                has_a[i][j] = has_a[i][j] | (has_a[i][k] & is_a[k][j])

    for i in range(1, M+1):
        C1, R, C2 = map(str, sys.stdin.readline().split())

        if (C1 == C2) and R == "is-a":
            print("Query {}: true".format(i))
            continue

        if R == "is-a":
            if is_a[data_[C1]][data_[C2]]:
                print("Query {}: true".format(i))
            else:
                print("Query {}: false".format(i))
        elif R == "has-a":
            if has_a[data_[C1]][data_[C2]]:
                print("Query {}: true".format(i))
            else:
                print("Query {}: false".format(i))
solution()

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

Categories:

Updated:

Leave a comment