結果

問題 No.1078 I love Matrix Construction
ユーザー tamatotamato
提出日時 2020-06-13 17:40:59
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 848 ms / 2,000 ms
コード長 3,748 bytes
コンパイル時間 196 ms
コンパイル使用メモリ 82,308 KB
実行使用メモリ 185,900 KB
最終ジャッジ日時 2024-06-25 15:54:10
合計ジャッジ時間 10,789 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 45 ms
55,436 KB
testcase_01 AC 43 ms
54,876 KB
testcase_02 AC 225 ms
93,180 KB
testcase_03 AC 369 ms
115,972 KB
testcase_04 AC 517 ms
130,284 KB
testcase_05 AC 445 ms
122,100 KB
testcase_06 AC 229 ms
92,732 KB
testcase_07 AC 165 ms
83,352 KB
testcase_08 AC 427 ms
122,584 KB
testcase_09 AC 138 ms
80,044 KB
testcase_10 AC 848 ms
185,900 KB
testcase_11 AC 501 ms
132,416 KB
testcase_12 AC 700 ms
165,244 KB
testcase_13 AC 768 ms
178,260 KB
testcase_14 AC 563 ms
146,188 KB
testcase_15 AC 728 ms
170,560 KB
testcase_16 AC 171 ms
81,824 KB
testcase_17 AC 42 ms
55,184 KB
testcase_18 AC 207 ms
88,632 KB
testcase_19 AC 296 ms
102,896 KB
testcase_20 AC 290 ms
102,592 KB
testcase_21 AC 96 ms
77,944 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

mod = 1000000007
eps = 10**-9


def main():
    import sys
    from collections import deque
    input = sys.stdin.readline

    from collections import deque

    # compressed[v]: 縮約後のグラフで縮約前のvが属する頂点
    # num: 縮約後のグラフの頂点数
    def SCC(adj, adj_rev):
        N = len(adj) - 1
        seen = [0] * (N + 1)
        compressed = [0] * (N + 1)
        order = []

        for v0 in range(1, N + 1):
            if seen[v0]:
                continue
            st = deque()
            st.append(v0)
            while st:
                v = st.pop()
                if v < 0:
                    order.append(-v)
                else:
                    if seen[v]:
                        continue
                    seen[v] = 1
                    st.append(-v)
                    for u in adj[v]:
                        st.append(u)

        seen = [0] * (N + 1)
        num = 0
        for v0 in reversed(order):
            if seen[v0]:
                continue
            num += 1
            st = deque()
            st.append(v0)
            seen[v0] = 1
            compressed[v0] = num
            while st:
                v = st.pop()
                for u in adj_rev[v]:
                    if seen[u]:
                        continue
                    seen[u] = 1
                    compressed[u] = num
                    st.append(u)

        return num, compressed

    # 縮約後のグラフを構築
    # 先にSCC()を実行してnum, compressedを作っておく
    def construct(adj, num, compressed):
        N = len(adj) - 1
        adj_compressed = [set() for _ in range(num + 1)]
        for v in range(1, N + 1):
            v_cmp = compressed[v]
            for u in adj[v]:
                u_cmp = compressed[u]
                if v_cmp != u_cmp:
                    adj_compressed[v_cmp].add(u_cmp)
        return adj_compressed

    def fin():
        print(-1)
        exit()

    N = int(input())
    S = list(map(int, input().split()))
    T = list(map(int, input().split()))
    U = list(map(int, input().split()))

    def idx(i, j, flg):
        return i * N + j + 1 + flg * N*N

    adj = [[] for _ in range(N*N*2 + 1)]
    adj_rev = [[] for _ in range(N * N * 2 + 1)]
    for i in range(N):
        s = S[i] - 1
        t = T[i] - 1
        u = U[i]
        if u == 0:
            flg_s = 1
            flg_t = 1
        elif u == 1:
            flg_s = 0
            flg_t = 1
        elif u == 2:
            flg_s = 1
            flg_t = 0
        else:
            flg_s = 0
            flg_t = 0
        for j in range(N):
            a = idx(s, j, flg_s)
            b = idx(j, t, flg_t)
            if a > N*N:
                adj[a - N*N].append(b)
                adj_rev[b].append(a - N*N)
            else:
                adj[a + N*N].append(b)
                adj_rev[b].append(a + N*N)
            if b > N*N:
                adj[b - N*N].append(a)
                adj_rev[a].append(b - N*N)
            else:
                adj[b + N*N].append(a)
                adj_rev[a].append(b + N*N)

    _, G_idx = SCC(adj, adj_rev)
    for v in range(1, N*N+1):
        v_ = v + N*N
        if G_idx[v] == G_idx[v_]:
            fin()

    ans = [[0] * N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            v = idx(i, j, 0)
            v_ = idx(i, j, 1)
            if G_idx[v] < G_idx[v_]:
                ans[i][j] = 1
    for i in range(N):
        print(*ans[i])

    # check
    for i in range(N):
        s = S[i] - 1
        t = T[i] - 1
        u = U[i]
        for j in range(N):
            if u == ans[s][j] + ans[j][t] * 2:
                assert False


if __name__ == '__main__':
    main()
0