結果

問題 No.1078 I love Matrix Construction
ユーザー tamatotamato
提出日時 2020-06-12 22:38:56
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,376 bytes
コンパイル時間 269 ms
コンパイル使用メモリ 87,608 KB
実行使用メモリ 240,648 KB
最終ジャッジ日時 2023-09-06 10:48:22
合計ジャッジ時間 15,609 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 98 ms
72,092 KB
testcase_01 AC 95 ms
71,584 KB
testcase_02 AC 337 ms
101,708 KB
testcase_03 AC 551 ms
135,324 KB
testcase_04 AC 697 ms
158,780 KB
testcase_05 WA -
testcase_06 AC 352 ms
99,344 KB
testcase_07 AC 254 ms
86,276 KB
testcase_08 AC 605 ms
144,896 KB
testcase_09 WA -
testcase_10 AC 1,130 ms
240,648 KB
testcase_11 AC 740 ms
163,172 KB
testcase_12 AC 999 ms
210,000 KB
testcase_13 AC 1,088 ms
229,668 KB
testcase_14 AC 803 ms
180,092 KB
testcase_15 AC 1,028 ms
222,112 KB
testcase_16 WA -
testcase_17 AC 94 ms
71,928 KB
testcase_18 AC 306 ms
95,468 KB
testcase_19 AC 421 ms
115,036 KB
testcase_20 AC 432 ms
114,076 KB
testcase_21 AC 159 ms
79,108 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

mod = 1000000007
eps = 10**-9


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

    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)

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

    order.reverse()
    seen2 = [0] * (N*N*2 + 1)
    G = []
    G_idx = [-1] * (N*N*2 + 1)
    for v0 in order:
        if seen2[v0]:
            continue
        st = deque()
        st.append(v0)
        seen2[v0] = 1
        G.append([v0])
        G_idx[v0] = len(G) - 1
        while st:
            v = st.pop()
            for u in adj_rev[v]:
                if seen2[u]:
                    continue
                G[-1].append(u)
                G_idx[u] = G_idx[v0]
                seen2[u] = 1
                st.append(u)
    TF = [-1] * len(G)
    for k in range(len(G)):
        flg = 1
        for v in G[k]:
            if v > N*N:
                v_ = v - N*N
            else:
                v_ = v + N*N
            if G_idx[v] == G_idx[v_]:
                fin()
            if flg:
                kk = G_idx[v_]
                if TF[kk] != -1:
                    TF[k] = TF[kk] ^ 1
                    flg = 0
            else:
                kk = G_idx[v_]
                if TF[kk] != -1:
                    if TF[kk] == TF[k]:
                        fin()
        if flg:
            TF[k] = 1

    ans = [[0] * N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            v = idx(i, j, 0)
            ans[i][j] = TF[G_idx[v]]
    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:
                print(i, j)
    """


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